<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
    <head>
        <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />

        <meta property="og:title" content="Haskell 趣學指南" />
        <meta property="og:type" content="website" />
        <meta property="og:url" content="http://learnyouahaskell-zh-tw.csie.org" />
        <meta property="og:image" content="http://learnyouahaskell-zh-tw.csie.org/img/bird.png" />

        <style type="text/css">
            @import url(../css/style.css);
            @import url(../css/feedback.css);
        </style>
        <script type="text/javascript" src="../js/jquery.js"></script>
        <script type="text/javascript" src="../js/jquery.chili-2.2.js"></script>
        <script type="text/javascript" src="../js/script.js"></script>
        <script type="text/javascript" src="../js/html2canvas.js"></script>
        <script type="text/javascript" src="../js/jsfeedback.js"></script>
        <script type="text/javascript">
             ChiliBook.recipeFolder = "../js/chili/";  
             ChiliBook.automaticSelector = "pre";
        </script>
        <script type="text/javascript">
            $(function(){
                $('#feedback').click(function(){
                    $('body').feedback();
                })
            });
        </script>
        <script defer type="text/javascript">
            var _gaq = _gaq || [];
            _gaq.push(['_setAccount', 'UA-32830659-1']);
            _gaq.push(['_trackPageview']);

            (function() {
                var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true;
                ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
                    var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s);
            })();
        </script>
        <title>再来看看更多 Monad</title>
    </head>
    <body>
        <div id="header">
        </div>

        <div id="main">
            <ul class="nav">
                <li class="left">  <img src="../img/prv.png" alt="prev" /><a href="a-fistful-of-monads.html">来看看几种 Monad</a></li>
                <li class="center"><a href="chapters.html">目录</a></li>
                <li class="right"> <a href="zippers.html">Zippers 数据结构</a><img src="../img/nxt.png" alt="next" /></li>
            </ul>
            <a name="再来看看更多_Monad"></a><h1>再来看看更多 Monad</h1>

<img src="../img/clint.png" alt="" style="float:right" class="floatright" />
<p>我们已经看过 Monad 是如何接受具有 context 的值，并如何用函数操作他们 还有如何用 <code>&gt;&gt;=</code> 跟 <code>do</code> 来减轻我们对 context 的关注，集中精神在 value 本身。</p>

<p>我们也看过了 <code>Maybe</code> 是如何把值加上一个可能会失败的 context。我们学习到 List Monad 是如何加进多重结果的 context。我们也了解 <code>IO</code> Monad 如何运作，而且我们在知道什么是 Monad 之前就已经知道他了。</p>

<p>在这个章节，我们会介绍一些其他的 Monad。他们可以把值变成 monadic value，因此可以让我们的程序更简洁清晰。多见识几个 Monad 也可以敏锐我们对 Monad 的直觉。</p>

<p>我们即将要介绍的 Monad 都包含在 <code>mtl</code> 这个套建中。一个 Haskell package 包含了一堆模块。而 <code>mtl</code> 已经包含在 Haskell Platform 中，所以你可能不用另外安装。要检查你有没有这套件，你可以下 <code>ghc-pkg list</code>。这会列出你已经安装的套件，其中应该包含 <code>mtl</code> 后面接着对应的版号。</p>
<a name="你所不知道的_Writer_Monad"></a><h2>你所不知道的 Writer Monad</h2>


<p>我们已经看过 <code>Maybe</code>, list 以及 <code>IO</code> Monad。现在我们要来看看 <code>Writer</code> Monad。</p>

<p>相对于 <code>Maybe</code> 是加入可能失败的 context，list 是加入 non-deterministic 的 context，<code>Writer</code> 则是加进一个附加值的 context，好比 log 一般。<code>Writer</code> 可以让我们在计算的同时搜集所有 log 纪录，并汇集成一个 log 并附加在结果上。</p>

<p>例如我们想要附加一个 String 好说明我们的值在干么（有可能是为了除错）。想像有一个函数接受一个代表帮派人数的数字，然后会回传值告诉我们这是否算是一个庞大的帮派：</p>
<pre class="code">isBigGang :: Int -&gt; Bool  
isBigGang x = x &gt; 9</pre>
<p>现在我们希望他不只是回传 <code>True</code> 或 <code>False</code>，我们还希望他能够多回传一个字串代表 log。这很容易，只要多加一个 <code>String</code> 在 <code>Bool</code> 旁边就好了。</p>
<pre class="code">isBigGang :: Int -&gt; (Bool, String)  
isBigGang x = (x &gt; 9, "Compared gang size to 9.")</pre>
<p>我们现在回传了一个 Tuple，第一个元素是原来的布林值，第二个元素是一个 String。现在我们的值有了一个 context。</p>
<pre class="code">ghci&gt; isBigGang 3  
(False,"Compared gang size to 9.")  
ghci&gt; isBigGang 30  
(True,"Compared gang size to 9.")</pre><img src="../img/tuco.png" alt="" style="float:left" class="floatleft" />
<p>到目前为止都还不错，<code>isBigGang</code> 回传一个值跟他的 context。对于正常的数值来说这样的写法都能运作良好。但如果我们想要把一个已经具有 context 的值，像是 <code>(3, "Smallish gang.")</code>，喂给 <code>isBigGang</code> 呢？我们又面对了同样的问题：如果我们有一个能接受正常数值并回传一个具有 context 值的 function，那我们要如何喂给他一个具有 context 的值？</p>

<p>当我们在研究 <code>Maybe</code> monad 的时候，我们写了一个 <code>applyMaybe</code>。他接受一个 <code>Maybe a</code> 值跟一个 <code>a -&gt; Maybe b</code> 型态的函数，他会把 <code>Maybe a</code> 喂给这个 function，即便这个 function 其实是接受 <code>a</code> 而非 <code>Maybe a</code>。<code>applyMaybe</code> 有针对这样的 context 做处理，也就是会留意有可能发生的失败情况。但在 <code>a -&gt; Maybe b</code> 里面，我们可以只专心处理正常数值即可。因为 <code>applyMaybe</code> (之后变成了 <code>&gt;&gt;=</code>)会帮我们处理需要检查 <code>Nothing</code> 或 <code>Just</code> 的情况。</p>

<p>我们再来写一个接受附加 log 值的函数，也就是 <code>(a, String)</code> 型态的值跟 <code>a -&gt; (b, String)</code> 型态的函数。我们称呼这个函数为 <code>applyLog</code>。这个函数有的 context 是附加 log 值，而不是一个可能会失败的 context，因此 <code>applyLog</code> 会确保原有的 log 被保留，并附上从函数产生出的新的 log。这边我们来看一下实作：</p>
<pre class="code">applyLog :: (a,String) -&gt; (a -&gt; (b,String)) -&gt; (b,String)  
applyLog (x,log) f = let (y,newLog) = f x in (y,log ++ newLog)</pre>
<p>当我们想把一个具有 context 的值喂给一个函数的时候，我们会尝试把值跟他的 context 分开，然后把值喂给函数再重新接回 context。在 <code>Maybe</code> monad 的情况，我们检查值是否为 <code>Just x</code>，如果是，便将 <code>x</code> 喂给函数。而在 log 的情况，我们知道 pair 的其中一个 component 是 log 而另一个是值。所以我们先取出值 <code>x</code>，将 <code>f</code> apply 到 <code>x</code>，便获取 <code>(y,newLog)</code>，其中 <code>y</code> 是新的值而 <code>newLog</code> 则是新的 log。但如果我们回传 <code>newLog</code>，旧的 log 便不会包含进去，所以我们要回传的是 <code>(y, log ++ newLog)</code>。我们用 <code>++</code> 来把新的 log 接到旧的上面。</p>

<p>来看看 <code>applyLog</code> 运作的情形：</p>
<pre class="code">ghci&gt; (3, "Smallish gang.") `applyLog` isBigGang  
(False,"Smallish gang.Compared gang size to 9")  
ghci&gt; (30, "A freaking platoon.") `applyLog` isBigGang  
(True,"A freaking platoon.Compared gang size to 9")</pre>
<p>跟之前的结果很像，只差在我们多了伴随产生的 log。再来多看几个例子：</p>
<pre class="code">ghci&gt; ("Tobin","Got outlaw name.") `applyLog` (\x -&gt; (length x, "Applied length."))  
(5,"Got outlaw name.Applied length.")  
ghci&gt; ("Bathcat","Got outlaw name.") `applyLog` (\x -&gt; (length x, "Applied length"))  
(7,"Got outlaw name.Applied length")</pre>
<p>可以看到在 lambda 里面 <code>x</code> 只是个正常的字串而不是 tuple，且 <code>applyLog</code> 帮我们处理掉附加 log 的动作。</p>
<a name="Monoids_的好处"></a><h3>Monoids 的好处</h3>

<blockquote>
<p>请确定你了解什么是 Monoids。</p>
</blockquote>

<p>到目前为止 <code>applyLog</code> 接受 <code>(a,String)</code> 型态的值，但为什么 log 一定要是 <code>String</code> 呢？我们使用 <code>++</code> 来附加新的 log，难道 <code>++</code> 并不能运作在任何形式的 list，而一定要限制我们在 <code>String</code> 上呢？我们当然可以摆脱 <code>String</code>，我们可以如下改变他的型态：</p>
<pre class="code">applyLog :: (a,[c]) -&gt; (a -&gt; (b,[c])) -&gt; (b,[c])</pre>
<p>我们用一个 List 来代表 Log。包含在 List 中的元素型态必须跟原有的 List 跟回传的 List 型态相同，否则我们没办法用 <code>++</code> 来把他们接起来。</p>

<p>这能够运作在 bytestring 上吗？绝对没问题。只是我们现在的型态只对 List 有效。我们必须要另外做一个 bytestring 版本的 <code>applyLog</code>。但我们注意到 List 跟 bytestring 都是 monoids。因此他们都是 <code>Monoid</code> type class 的 instance，那代表他们都有实作 <code>mappend</code>。对 List 以及 bytestring 而言，<code>mappend</code> 都是拿来串接的。</p>
<pre class="code">ghci&gt; [1,2,3] `mappend` [4,5,6]  
[1,2,3,4,5,6]  
ghci&gt; B.pack [99,104,105] `mappend` B.pack [104,117,97,104,117,97]  
Chunk "chi" (Chunk "huahua" Empty)</pre>
<p>修改后我们的 <code>applyLog</code> 可以运作在任何 monoid 上。我们必须要修改型态宣告来表示这件事，同时也要在实作中把 <code>++</code> 改成 <code>mappend</code>：</p>
<pre class="code">applyLog :: (Monoid m) =&gt; (a,m) -&gt; (a -&gt; (b,m)) -&gt; (b,m)  
applyLog (x,log) f = let (y,newLog) = f x in (y,log `mappend` newLog)</pre>
<p>由于现在包含的值可以是任何 monoid，我们不再需要把 tuple 想成包含一个值跟对应的 log，我们可以想成他包含一个值跟一个对应的 monoid。举例来说，可以说我们有一个 tuple 包含一个产品名称跟一个符合 monoid 特性的产品价格。我们可以定义一个 <code>Sum</code> 的 newtype 来保证我们在操作产品的时候也会把价钱跟着加起来。</p>
<pre class="code">import Data.Monoid  
  
type Food = String  
type Price = Sum Int  

addDrink :: Food -&gt; (Food,Price)  
addDrink "beans" = ("milk", Sum 25)  
addDrink "jerky" = ("whiskey", Sum 99)  
addDrink _ = ("beer", Sum 30)</pre>
<p>我们用 string 来代表食物，用 <code>newtype</code> 重新定义 <code>nInt</code> 为 <code>Sum</code>，来追踪总共需要花多少钱。可以注意到我们用 <code>mappend</code> 来操作 <code>Sum</code> 的时候，价钱会被一起加起来。</p>
<pre class="code">ghci&gt; Sum 3 `mappend` Sum 9  
Sum {getSum = 12}</pre>
<p><code>addDrink</code> 的实作很简单，如果我们想吃豆子，他会回传 <code>"milk"</code> 以及伴随的 <code>Sum 25</code>，同样的如果我们要吃 "jerky"，他就会回传 "whiskey"，要吃其他东西的话，就会回传 "beer"。乍看之下这个函数没什么特别，但如果用 <code>applyLog</code> 的话就会有趣些。</p>
<pre class="code">ghci&gt; ("beans", Sum 10) `applyLog` addDrink  
("milk",Sum {getSum = 35})  
ghci&gt; ("jerky", Sum 25) `applyLog` addDrink  
("whiskey",Sum {getSum = 124})  
ghci&gt; ("dogmeat", Sum 5) `applyLog` addDrink  
("beer",Sum {getSum = 35})</pre>
<p>牛奶价值 <code>25</code> 美分，但如果我们也吃了价值 <code>10</code> 美分的豆子的话，总共需要付 <code>35</code> 美分。这样很清楚地展示了伴随的值不一定需要是 log，他可以是任何 monoid。至于两个值要如何结合，那要看 monoid 中怎么定义。当我们需要的是 log 的时候，他们是串接，但这个 case 里面，数字是被加起来。</p>

<p>由于 <code>addDrink</code> 回传一个 <code>(Food,Price)</code>，我们可以再把结果重新喂给 <code>addDrink</code>，这可以很容易告诉我们总共喝了多少钱：</p>
<pre class="code">ghci&gt; ("dogmeat", Sum 5) `applyLog` addDrink `applyLog` addDrink  
("beer",Sum {getSum = 65})</pre>
<p>将狗食跟 30 美分的啤酒加在一起会得到 <code>("beer", Sum 35)</code>。如果我们用 <code>applyLog</code> 将上面的结果再喂给 <code>addDrink</code>，我们会得到 <code>("beer", Sum 65)</code> 这样的结果。</p>
<a name="The_Writer_type"></a><h3>The Writer type</h3>


<p>我们认识了一个附加 monoid 的值其实表现出来的是一个 monad，我们来再来看看其他类似的 <code>Monad</code> instance。<code>Control.Monad.Writer</code> 这模块含有 <code>Writer w a</code> 的一个型态，里面定义了他 <code>Monad</code> 的 instance，还有一些操作这些值的函数。</p>

<p>首先，我们来看一下型态。要把一个 monoid 附加给一个值，只需要定义一个 tuple 就好了。<code>Writer w a</code> 这型态其实是一个 <code>newtype</code> wrapper。他的定义很简单：</p>
<pre class="code">newtype Writer w a = Writer { runWriter :: (a, w) }</pre>
<p>他包在一个 <code>newtype</code> 里面，并且可以是一个 <code>Monad</code> 的 instance，而且这样定义的好处是可以跟单纯 tuple 的型态区分开来。<code>a</code> 这个型态参数代表是包含的值的型态，而 <code>w</code> 则是附加的 monoid 的型态。</p>

<p>他 <code>Monad</code> instance 的定义如下：</p>
<pre class="code">instance (Monoid w) =&gt; Monad (Writer w) where  
    return x = Writer (x, mempty)  
    (Writer (x,v)) &gt;&gt;= f = let (Writer (y, v')) = f x in Writer (y, v `mappend` v')</pre><img src="../img/angeleyes.png" alt="" style="float:right" class="floatright" />
<p>首先，我们来看看 <code>&gt;&gt;=</code>。他的实作基本上就是 <code>applyLog</code>，只是我们的 tuple 现在是包在一个 <code>Writer</code> 的 <code>newtype</code> 中，我们可以用 pattern matching 的方式把他给 unwrap。我们将 <code>x</code> 喂给 <code>f</code>。这会回给我们 <code>Writer w a</code>。接着可以用 <code>let</code> expression 来做 pattern matching。把结果绑定到 <code>y</code> 这个名字上，然后用 <code>mappend</code> 来结合旧的 monoid 值跟新的 monoid 值。最后把结果跟 monoid 值用 <code>Writer</code> constructor 包起来，形成我们最后的 <code>Writer</code> value。</p>

<p>那 <code>return</code> 呢？回想 <code>return</code> 的作用是接受一个值，并回传一个具有意义的最小 context 来装我们的值。那究竟什么样的 context 可以代表我们的 <code>Writer</code> 呢？如果我们希望 monoid 值所造成的影响愈小愈好，那 <code>mempty</code> 是个合理的选择。<code>mempty</code> 是被当作 identity monoid value，像是 <code>""</code> 或 <code>Sum 0</code>，或是空的 bytestring。当我们对 <code>mempty</code> 用 <code>mappend</code> 跟其他 monoid 值结合，结果会是其他的 monoid 值。所以如果我们用 <code>return</code> 来做一个 <code>Writer</code>，然后用 <code>&gt;&gt;=</code> 来喂给其他的函数，那函数回传的便是算出来的 monoid。下面我们试着用 <code>return</code> 搭配不同 context 来回传 <code>3</code>：</p>
<pre class="code">ghci&gt; runWriter (return 3 :: Writer String Int)  
(3,"")  
ghci&gt; runWriter (return 3 :: Writer (Sum Int) Int)  
(3,Sum {getSum = 0})  
ghci&gt; runWriter (return 3 :: Writer (Product Int) Int)  
(3,Product {getProduct = 1})</pre>
<p>因为 <code>Writer</code> 并没有定义成 <code>Show</code> 的 instance，我们必须用 <code>runWriter</code> 来把我们的 <code>Writer</code> 转成正常的 tuple。对于 <code>String</code>，monoid 的值就是空字串。而对于 <code>Sum</code> 来说则是 <code>0</code>，因为 <code>0</code> 加上其他任何值都会是对方。而对 <code>Product</code> 来说，则是 <code>1</code>。</p>

<p>这里的 <code>Writer</code> instance 并没有定义 <code>fail</code>，所以如果 pattern matching 失败的话，就会调用 <code>error</code>。</p>
<a name="Using_do_notation_with_Writer"></a><h3>Using do notation with Writer</h3>


<p>既然我们定义了 <code>Monad</code> 的 instance，我们自然可以用 <code>do</code> 串接 <code>Writer</code> 型态的值。这在我们需要对一群 <code>Writer</code> 型态的值做处理时显得特别方便。就如其他的 monad，我们可以把他们当作具有 context 的值。在现在这个 case 中，所有的 monoid 的值都会用 <code>mappend</code> 来连接起来并得到最后的结果。这边有一个简单的范例，我们用 <code>Writer</code> 来相乘两个数。</p>
<pre class="code">import Control.Monad.Writer  
  
logNumber :: Int -&gt; Writer [String] Int  
logNumber x = Writer (x, ["Got number: " ++ show x])  
  
multWithLog :: Writer [String] Int  
multWithLog = do  
    a &lt;- logNumber 3  
    b &lt;- logNumber 5  
    return (a*b)</pre>
<p><code>logNumber</code> 接受一个数并把这个数做成一个 <code>Writer</code>。我们再用一串 string 来当作我们的 monoid 值，每一个数都跟着一个只有一个元素的 list，说明我们只有一个数。<code>multWithLog</code> 式一个 <code>Writer</code>，他将 <code>3</code> 跟 <code>5</code> 相乘并确保相乘的纪录有写进最后的 log 中。我们用 <code>return</code> 来做成 <code>a*b</code> 的结果。我们知道 <code>return</code> 会接受某个值并加上某个最小的 context，我们可以确定他不会多添加额外的 log。如果我们执行程序会得到：</p>
<pre class="code">ghci&gt; runWriter multWithLog  
(15,["Got number: 3","Got number: 5"])</pre>
<p>有时候我们就是想要在某个时间点放进某个 Monoid value。<code>tell</code> 正是我们需要的函数。他实作了 <code>MonadWriter</code> 这个 type class，而且在当 <code>Writer</code> 用的时候也能接受一个 monoid value，好比说 <code>["This is going on"]</code>。我们能用他来把我们的 monoid value 接到任何一个 dummy value <code>()</code> 上来形成一个 Writer。当我们拿到的结果是 <code>()</code> 的时候，我们不会把他绑定到变量上。来看一个 <code>multWithLog</code> 的范例：</p>
<pre class="code">multWithLog :: Writer [String] Int  
multWithLog = do  
    a &lt;- logNumber 3  
    b &lt;- logNumber 5  
    tell ["Gonna multiply these two"]  
    return (a*b)</pre>
<p><code>return (a*b)</code> 是我们的最后一行，还记得在一个 <code>do</code> 中的最后一行代表整个 <code>do</code> 的结果。如果我们把 <code>tell</code> 摆到最后，则 <code>do</code> 的结果则会是 <code>()</code>。我们会因此丢掉乘法运算的结果。除此之外，log 的结果是不变的。</p>
<pre class="code">ghci&gt; runWriter multWithLog  
(15,["Got number: 3","Got number: 5","Gonna multiply these two"])</pre><a name="Adding_logging_to_programs"></a><h3>Adding logging to programs</h3>


<p>欧几里得算法是找出两个数的最大公因数。Haskell 已经提供了 <code>gcd</code> 的函数，但我们来实作一个具有 log 功能的 gcd：</p>
<pre class="code">gcd' :: Int -&gt; Int -&gt; Int  
gcd' a b   
    | b == 0    = a  
    | otherwise = gcd' b (a `mod` b)</pre>
<p>算法的内容很简单。首先他检查第二个数字是否为零。如果是零，那就回传第一个数字。如果不是，那结果就是第二个数字跟将第一个数字除以第二个数字的余数两个数字的最大公因数。举例来说，如果我们想知道 8 跟 3 的最大公因数，首先可以注意到 3 不是 0。所以我们要求的是 3 跟 2 的最大公因数(8 除以 3 余二)。接下去我可以看到 2 不是 0，所以我们要再找 2 跟 1 的最大公因数。同样的，第二个数不是 0，所以我们再找 1 跟 0 的最大公因数。最后第二个数终于是 0 了，所以我们得到最大公因数是 1。</p>
<pre class="code">ghci&gt; gcd' 8 3  
1</pre>
<p>答案真的是这样。接着我们想加进 context，context 会是一个 monoid value 并且像是一个 log 一样。就像之前的范例，我们用一串 string 来当作我们的 monoid。所以 <code>gcd'</code> 会长成这样：</p>
<pre class="code">gcd' :: Int -&gt; Int -&gt; Writer [String] Int</pre>
<p>而他的代码会像这样：</p>
<pre class="code">import Control.Monad.Writer  
  
gcd' :: Int -&gt; Int -&gt; Writer [String] Int  
gcd' a b  
  | b == 0 = do  
      tell ["Finished with " ++ show a]  
      return a  
  | otherwise = do  
      tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)]  
      gcd' b (a `mod` b)</pre>
<p>这个函数接受两个 <code>Int</code> 并回传一个 <code>Writer [String] Int</code>，也就是说是一个有 log context 的 <code>Int</code>。当 <code>b</code> 等于 <code>0</code> 的时候，我们用一个 <code>do</code> 来组成一个 <code>Writer</code> 的值。我们先用 <code>tell</code> 来写入我们的 log，然后用 <code>return</code> 来当作 <code>do</code> 的结果。当然我们也可以这样写：</p>
<pre class="code">Writer (a, ["Finished with " ++ show a])</pre>
<p>但我想 <code>do</code> 的表达方式是比较容易阅读的。接下来我们看看当 <code>b</code> 不等于 <code>0</code> 的时候。我们会把 <code>mod</code> 的使用情况写进 log。然后在 <code>do</code> 当中的第二行递归调用 <code>gcd'</code>。<code>gcd'</code> 现在是回传一个 <code>Writer</code> 的型态，所以 <code>gcd' b (a `mod` b)</code> 这样的写法是完全没问题的。</p>

<p>尽管去 trace 这个 <code>gcd'</code> 对于理解十分有帮助，但我想了解整个大概念，把值视为具有 context 是更加有用的。</p>

<p>接着来试试跑我们的 <code>gcd'</code>，他的结果会是 <code>Writer [String] Int</code>，如果我们把他从 <code>newtype</code> 中取出来，我们会拿到一个 tuple。tuple 的第一个部份就是我们要的结果：</p>
<pre class="code">ghci&gt; fst $ runWriter (gcd' 8 3)  
1</pre>
<p>至于 log 呢，由于 log 是一连串 string，我们就用 <code>mapM_ putStrLn</code> 来把这些 string 印出来：</p>
<pre class="code">ghci&gt; mapM_ putStrLn $ snd $ runWriter (gcd' 8 3)  
8 mod 3 = 2  
3 mod 2 = 1  
2 mod 1 = 0  
Finished with 1</pre>
<p>把普通的算法转换成具有 log 是很棒的经验，我们不过是把普通的 value 重写成 Monadic value，剩下的就靠 <code>&gt;&gt;=</code> 跟 <code>Writer</code> 来帮我们处理一切。用这样的方法我们几乎可以对任何函数加上 logging 的功能。我们只要把普通的值换成 <code>Writer</code>，然后把一般的函数调用换成 <code>&gt;&gt;=</code> (当然也可以用 <code>do</code>)</p>
<a name="Inefficient_list_construction"></a><h3>Inefficient list construction</h3>


<p>当制作 <code>Writer</code> Monad 的时候，要特别注意你是使用哪种 monoid。使用 list 的话性能有时候是没办法接受的。因为 list 是使用 <code>++</code> 来作为 <code>mappend</code> 的实现。而 <code>++</code> 在 list 很长的时候是非常慢的。</p>

<p>在之前的 <code>gcd'</code> 中，log 并不会慢是因为 list append 的动作实际上看起来是这样：</p>
<pre class="code">a ++ (b ++ (c ++ (d ++ (e ++ f))))</pre>
<p>list 是建立的方向是从左到右，当我们先建立左边的部份，而把另一串 list 加到右边的时候性能会不错。但如果我们不小心使用，而让 <code>Writer</code> monad 实际在操作 list 的时候变成像这样的话。</p>
<pre class="code">((((a ++ b) ++ c) ++ d) ++ e) ++ f</pre>
<p>这会让我们的操作是 left associative，而不是 right associative。这非常没有效率，因为每次都是把右边的部份加到左边的部份，而左边的部份又必须要从头开始建起。</p>

<p>下面这个函数跟 <code>gcd'</code> 差不多，只是 log 的顺序是相反的。他先纪录剩下的操作，然后纪录现在的步骤。</p>
<pre class="code">import Control.Monad.Writer  
  
gcdReverse :: Int -&gt; Int -&gt; Writer [String] Int  
gcdReverse a b  
  | b == 0 = do  
      tell ["Finished with " ++ show a]  
      return a  
    | otherwise = do  
      result &lt;- gcdReverse b (a `mod` b)  
      tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)]  
      return result</pre>
<p>他先递归调用，然后把结果绑定到 <code>result</code>。然后把目前的动作写到 log，在递归的结果之后。最后呈现的就是完整的 log。</p>
<pre class="code">ghci&gt; mapM_ putStrLn $ snd $ runWriter (gcdReverse 8 3)  
Finished with 1  
2 mod 1 = 0  
3 mod 2 = 1  
8 mod 3 = 2</pre>
<p>这没效率是因为他让 <code>++</code> 成为 left associative 而不是 right associative。</p>
<a name="Difference_lists"></a><h3>Difference lists</h3>

<img src="../img/cactus.png" alt="" style="float:left" class="floatleft" />
<p>由于 list 在重复 append 的时候显得低效，我们最好能使用一种支持高效 appending 的数据结构。其中一种就是 difference list。difference list 很类似 list，只是他是一个函数。他接受一个 list 并 prepend 另一串 list 到他前面。一个等价于 <code>[1,2,3]</code> 的 difference list 是这样一个函数 <code>\xs -&gt; [1,2,3] ++ xs</code>。一个等价于 <code>[]</code> 的 difference list 则是 <code>\xs -&gt; [] ++ xs</code>。</p>

<p>Difference list 最酷的地方在于他支持高效的 appending。当我们用 <code>++</code> 来实现 appending 的时候，他必须要走到左边的 list 的尾端，然后把右边的 list 一个个从这边接上。那 difference list 是怎么作的呢？appending 两个 difference list 就像这样</p>
<pre class="code">f `append` g = \xs -&gt; f (g xs)</pre>
<p><code>f</code> 跟 <code>g</code> 这边是两个函数，他们都接受一个 list 并 prepend 另一串 list。举例来说，如果 <code>f</code> 代表 <code>("dog"++)</code>（可以写成 <code>\xs -&gt; "dog" ++ xs</code>）而 <code>g</code> 是 <code>("meat"++)</code>，那 <code>f `append` g</code> 就会做成一个新的函数，等价于：</p>
<pre class="code">\xs -&gt; "dog" ++ ("meat" ++ xs)</pre>
<p>append 两个 difference list 其实就是用一个函数，这函数先喂一个 list 给第一个 difference list，然后再把结果喂给第二个 difference list。</p>

<p>我们可以用一个 <code>newtype</code> 来包起来</p>
<pre class="code">newtype DiffList a = DiffList { getDiffList :: [a] -&gt; [a] }</pre>
<p>我们包起来的型态是 <code>[a] -&gt; [a]</code>，因为 difference list 不过就是一个转换一个 list 到另一个 list 的函数。要把普通 list 转换成 difference list 也很容易。</p>
<pre class="code">toDiffList :: [a] -&gt; DiffList a  
toDiffList xs = DiffList (xs++)  
  
fromDiffList :: DiffList a -&gt; [a]  
fromDiffList (DiffList f) = f []</pre>
<p>要把一个普通 list 转成 difference list 不过就是照之前定义的，作一个 prepend 另一个 list 的函数。由于 difference list 只是一个 prepend 另一串 list 的一个函数，假如我们要转回来的话，只要喂给他空的 list 就行了。</p>

<p>这边我们给一个 difference list 的 <code>Monoid</code> 定义</p>
<pre class="code">instance Monoid (DiffList a) where  
    mempty = DiffList (\xs -&gt; [] ++ xs)  
    (DiffList f) `mappend` (DiffList g) = DiffList (\xs -&gt; f (g xs))</pre>
<p>我们可以看到 <code>mempty</code> 不过就是 <code>id</code>，而 <code>mappend</code> 其实是 function composition。</p>
<pre class="code">ghci&gt; fromDiffList (toDiffList [1,2,3,4] `mappend` toDiffList [1,2,3])  
[1,2,3,4,1,2,3]</pre>
<p>现在我们可以用 difference list 来加速我们的 <code>gcdReverse</code></p>
<pre class="code">import Control.Monad.Writer  
  
gcd' :: Int -&gt; Int -&gt; Writer (DiffList String) Int  
gcd' a b  
  | b == 0 = do  
      tell (toDiffList ["Finished with " ++ show a])  
      return a  
  | otherwise = do  
      result &lt;- gcd' b (a `mod` b)  
      tell (toDiffList [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)])  
      return result</pre>
<p>我们只要把 monoid 的型态从 <code>[String]</code> 改成 <code>DiffList String</code>，并在使用 <code>tell</code> 的时候把普通的 list 用 <code>toDiffList</code> 转成 difference list 就可以了。</p>
<pre class="code">ghci&gt; mapM_ putStrLn . fromDiffList . snd . runWriter $ gcdReverse 110 34  
Finished with 2  
8 mod 2 = 0  
34 mod 8 = 2  
110 mod 34 = 8</pre>
<p>我们用 <code>runWriter</code> 来取出 <code>gcdReverse 110 34</code> 的结果，然后用 <code>snd</code> 取出 log，并用 <code>fromDiffList</code> 转回普通的 list 印出来。</p>
<a name="Comparing_Performance"></a><h3>Comparing Performance</h3>


<p>要体会 Difference List 能如何增进效率，考虑一个从某数数到零的 case。我们纪录的时候就像 <code>gcdReverse</code> 一样是反过来记的，所以在 log 中实际上是从零数到某个数。</p>
<pre class="code">finalCountDown :: Int -&gt; Writer (DiffList String) ()  
finalCountDown 0 = do  
    tell (toDiffList ["0"])  
finalCountDown x = do  
    finalCountDown (x-1)  
    tell (toDiffList [show x])</pre>
<p>如果我们喂 <code>0</code>，他就只 log 0。如果喂其他正整数，他会先倒数到 <code>0</code> 然后 append 那些数到 log 中，所以如果我们调用 <code>finalCountDown</code> 并喂给他 <code>100</code>，那 log 的最后一笔就会是 <code>"100"</code>。</p>

<p>如果你把这个函数 load 进 GHCi 中并喂给他一个比较大的整数 <code>500000</code>，你会看到他无停滞地从 <code>0</code> 开始数起：</p>
<pre class="code">ghci&gt; mapM_ putStrLn . fromDiffList . snd . runWriter $ finalCountDown 500000  
0  
1  
2</pre>
<p>但如果我们用普通的 list 而不用 difference list</p>
<pre class="code">finalCountDown :: Int -&gt; Writer [String] ()  
finalCountDown 0 = do  
    tell ["0"]  
finalCountDown x = do  
    finalCountDown (x-1)  
    tell [show x]</pre>
<p>并下同样的指令</p>
<pre class="code">ghci&gt; mapM_ putStrLn . snd . runWriter $ finalCountDown 500000</pre>
<p>我们会看到整个运算卡卡的。</p>

<p>当然这不是一个严谨的测试方法，但足以表显出 difference list 是比较有效率的写法。</p>
<a name="Reader_Monad"></a><h2>Reader Monad</h2>

<img src="../img/revolver.png" alt="" style="float:left" class="floatleft" />
<p>在讲 Applicative 的章节中，我们说过了 <code>(-&gt;) r</code> 的型态只是 <code>Functor</code> 的一个 instance。要将一个函数 <code>f</code> map over 一个函数 <code>g</code>，基本上等价于一个函数，他可以接受原本 <code>g</code> 接受的参数，先套用 <code>g</code> 然后再把其结果丢给 <code>f</code>。</p>
<pre class="code">ghci&gt; let f = (*5)  
ghci&gt; let g = (+3)
ghci&gt; (fmap f g) 8</pre>
<p>我们已经见识过函数当作 applicative functors 的例子。这样能让我们对函数的结果直接进行操作。</p>
<pre class="code">ghci&gt; let f = (+) &lt;$&gt; (*2) &lt;*&gt; (+10)
ghci&gt; f 3
19</pre>
<p><code>(+) &lt;$&gt; (*2) &lt;*&gt; (+10)</code> 代表一个函数，他接受一个数值，分别把这数值交给 <code>(*2)</code> 跟 <code>(+10)</code>。然后把结果加起来。例如说，如果我们喂 <code>3</code> 给这个函数，他会分别对 <code>3</code> 做 <code>(*2)</code> 跟 <code>(+10)</code> 的动作。而得到 <code>6</code> 跟 <code>13</code>。然后调用 <code>(+)</code>，而得到 <code>19</code>。</p>

<p>其实 <code>(-&gt;) r</code> 不只是一个 functor 跟一个 applicative functor，他也是一个 monad。就如其他 monadic value 一般，一个函数也可以被想做是包含一个 context 的。这个 context 是说我们期待某个值，他还没出现，但我们知道我们会把他当作函数的参数，调用函数来得到结果。</p>

<p>我们已经见识到函数是怎样可以看作 functor 或是 applicative functors 了。再来让我们看看当作 <code>Monad</code> 的一个 instance 时会是什么样子。你可以在 <code>Control.Monad.Instances</code> 里面找到，他看起来像这样：</p>
<pre class="code">instance Monad ((-&gt;) r) where  
    return x = \_ -&gt; x  
    h &gt;&gt;= f = \w -&gt; f (h w) w</pre>
<p>我们之前已经看过函数的 <code>pure</code> 实作了，而 <code>return</code> 差不多就是 <code>pure</code>。他接受一个值并把他放进一个 minimal context 里面。而要让一个函数能够是某个定值的唯一方法就是让他完全忽略他的参数。</p>

<p>而 <code>&gt;&gt;=</code> 的实作看起来有点难以理解，我们可以仔细来看看。当我们使用 <code>&gt;&gt;=</code> 的时候，喂进去的是一个 monadic value，处理他的是一个函数，而吐出来的也是一个 monadic value。在这个情况下，当我们将一个函数喂进一个函数，吐出来的也是一个函数。这就是为什么我们在最外层使用了一个 lambda。在我们目前看过的实作中，<code>&gt;&gt;=</code> 几乎都是用 lambda 将内部跟外部隔开来，然后在内部来使用 <code>f</code>。这边也是一样的道理。要从一个函数得到一个结果，我们必须喂给他一些东西，这也是为什么我们先用 <code>(h w)</code> 取得结果，然后将他丢给 <code>f</code>。而 <code>f</code> 回传一个 monadic value，在这边这个 monadic value 也就是一个函数。我们再把 <code>w</code> 喂给他。</p>

<p>如果你还不太懂 <code>&gt;&gt;=</code> 怎么写出来的，不要担心，因为接下来的范例会让你晓得这真的是一个简单的 Monad。我们造一个 <code>do</code> expression 来使用这个 Monad。</p>
<pre class="code">import Control.Monad.Instances  
  
addStuff :: Int -&gt; Int  
addStuff = do  
  a &lt;- (*2)  
  b &lt;- (+10)  
  return (a+b)</pre>
<p>这跟我们之前写的 applicative expression 差不多，只差在他是运作在 monad 上。一个 <code>do</code> expression 的结果永远会是一个 monadic vlaue，这个也不例外。而这个 monadic value 其实是一个函数。只是在这边他接受一个数字，然后套用 <code>(*2)</code>，把结果绑定到 <code>a</code> 上面。而 <code>(+10)</code> 也同用被套用到同样的参数。结果被绑定到 <code>b</code> 上。<code>return</code> 就如其他 monad 一样，只是制作一个简单的 monadic value 而不会作多余的事情。这让整个函数的结果是 <code>a+b</code>。如果我们试着跑跑看，会得到之前的结果。</p>
<pre class="code">ghci&gt; addStuff 3  
19</pre>
<p>其中 <code>3</code> 会被喂给 <code>(*2)</code> 跟 <code>(+10)</code>。而且他也会被喂给 <code>return (a+b)</code>，只是他会忽略掉 <code>3</code> 而永远回传 <code>a+b</code> 正因为如此，function monad 也被称作 reader monad。所有函数都从一个固定的地方读取。要写得更清楚一些，可以把 <code>addStuff</code> 改写如下：</p>
<pre class="code">addStuff :: Int -&gt; Int  
addStuff x = let  
    a = (*2) x  
    b = (+10) x  
    in a+b</pre>
<p>我们见识了把函数视作具有 context 的值很自然的可以表达成 reader monad。只要我们当作我们知道函数会回传什么值就好。他作的就是把所有的函数都黏在一起做成一个大的函数，然后把这个函数的参数都喂给全部组成的函数，这有点取出他们未来的值的意味。实作做完了然后 <code>&gt;&gt;=</code> 就会保证一切都能正常运作。</p>
<a name="State_Monad"></a><h2>State Monad</h2>

<img src="../img/texas.png" alt="" style="float:left" class="floatleft" />
<p>Haskell 是一个纯粹的语言，正因为如此，我们的程序是有一堆没办法改变全域状态或变量的函数所组成，他们只会作些处理并回传结果。这样的性质让我们很容易思考我们的程序在干嘛，因为我们不需要担心变量在某一个时间点的值是什么。然而，有一些领域的问题根本上就是依赖于随着时间而改变的状态。虽然我们也可以用 Haskell 写出这样的程序，但有时候写起来蛮痛苦的。这也是为什么 Haskell 要加进 State Monad 这个特性。这让我们在 Haskell 中可以容易地处理状态性的问题，并让其他部份的程序还是保持纯粹性。</p>

<p>当我们处理乱数的时候，我们的函数接受一个 random generator 并回传一个新的乱数跟一个新的 random generator。如果我们需要很多个乱数，我们可以用前一个函数回传的 random generator 继续做下去。当我们要写一个接受 <code>StdGen</code> 的函数并产生丢三个硬币结果的函数，我们会这样写：</p>
<pre class="code">threeCoins :: StdGen -&gt; (Bool, Bool, Bool)  
threeCoins gen =   
    let (firstCoin, newGen) = random gen  
        (secondCoin, newGen') = random newGen  
        (thirdCoin, newGen''') = random newGen'  
    in  (firstCoin, secondCoin, thirdCoin)</pre>
<p>他接受一个 <code>gen</code> 然后用 <code>random gen</code> 产生一个 <code>Bool</code> 型态的值以及新的 generator。要仿真丢第二个硬币的话，便使用新的 generator。在其他语言中，多半除了乱数之外不需要多回传一个 generator。那是因为我们可以对现有的进行修改。但 Haskell 是纯粹的语言，我们没办法那么做，所以我们必须要接受一个状态，产生结果然后回传一个新的状态，然后用新的状态来继续做下去。</p>

<p>一般来讲你应该不会喜欢这么写，在程序中有赤裸裸的状态，但我们又不想放弃 Haskell 的纯粹性质。这就是 State Monad 的好处了，他可以帮我们处理这些琐碎的事情，又让我们保持 Haskell 的纯粹性。</p>

<p>为了深入理解状态性的计算，我们先来看看应该给他们什么样的型态。我们会说一个状态性的计算是一个函数，他接受一个状态，回传一个值跟一个新的状态。写起来会像这样：</p>
<pre class="code">s -&gt; (a,s)</pre>
<p><code>s</code> 是状态的型态，而 <code>a</code> 是计算结果的型态。</p>
<blockquote>
<p>在其他的语言中，赋值大多是被当作会改变状态的操作。举例来说，当我们在命令式语言写 <code>x = 5</code>，这通常代表的是把 <code>5</code> 指定给 <code>x</code> 这变量。而且这边 <code>5</code> 是一个 expression。</p>

<p>如果你用函数语言的角度去思考，你可以把他想做是一个函数，接受一个状态，并回传结果跟新的状态。那新的状态代表所有已指定的值与新加入的变量。</p>
</blockquote>

<p>这种改变状态的计算，除了想做是一个接受状态并回传结果跟新状态的函数外，也可以想做是具有 context 的值。</p>

<p>实际的值是结果。然而要得到结果，我们必须要给一个初始的状态，才能得到结果跟最后的状态。</p>
<a name="Stack_and_Stones"></a><h3>Stack and Stones</h3>


<p>考虑现在我们要对一个堆叠的操作建立模型。你可以把东西推上堆叠顶端，或是把东西从顶端拿下来。如果你要的元素是在堆叠的底层的话，你必须要把他上面的东西都拿下来才能拿到他。</p>

<p>我们用一个 list 来代表我们的堆叠。而我们把 list 的头当作堆叠的顶端。为了正确的建立模型，我们要写两个函数：<code>pop</code> 跟 <code>push</code>。<code>pop</code> 会接受一个堆叠，取下一个元素并回传一个新的堆叠，这个新的堆叠不包含取下的元素。<code>push</code> 会接受一个元素，把他堆到堆叠中，并回传一个新的堆叠，其包含这个新的元素。</p>
<pre class="code">type Stack = [Int]  
  
pop :: Stack -&gt; (Int,Stack)  
pop (x:xs) = (x,xs)  

push :: Int -&gt; Stack -&gt; ((),Stack)  
push a xs = ((),a:xs)</pre>
<p>我们用 <code>()</code> 来当作 pushing 的结果，毕竟推上堆叠并不需要什么回传值，他的重点是在改变堆叠。注意到 <code>push</code> 跟 <code>pop</code> 都是改变状态的计算，可以从他们的型态看出来。</p>

<p>我们来写一段程序来仿真一个堆叠的操作。我们接受一个堆叠，把 <code>3</code> 推上去，然后取出两个元素。</p>
<pre class="code">stackManip :: Stack -&gt; (Int, Stack)  
stackManip stack = let  
    ((),newStack1) = push 3 stack  
    (a ,newStack2) = pop newStack1  
    in pop newStack2</pre>
<p>我们拿一个 <code>stack</code> 来作 <code>push 3 stack</code> 的动作，其结果是一个 tuple。tuple 的第一个部份是 <code>()</code>，而第二个部份是新的堆叠，我们把他命名成 <code>newStack1</code>。然后我们从 <code>newStack1</code> 上 pop 出一个数字。其结果是我们之前 push 上去的一个数字 <code>a</code>，然后把这个更新的堆叠叫做 <code>newStack2</code>。然后我们从 <code>newStack2</code> 上再 pop 出一个数字 <code>b</code>，并得到 <code>newStack3</code>。我们回传一个 tuple 跟最终的堆叠。</p>
<pre class="code">ghci&gt; stackManip [5,8,2,1]  
(5,[8,2,1])</pre>
<p>结果就是 <code>5</code> 跟新的堆叠 <code>[8,2,1]</code>。注意到 <code>stackManip</code> 是一个会改变状态的操作。我们把一堆会改变状态的操作绑在一起操作，有没有觉得很耳熟的感觉。</p>

<p><code>stackManip</code> 的程序有点冗长，因为我们要写得太详细，必须把状态给每个操作，然后把新的状态再喂给下一个。如果我们可以不要这样作的话，那程序应该会长得像这样：</p>
<pre class="code">stackManip = do  
    push 3  
    a &lt;- pop  
    pop</pre>
<p>这就是 State Monad 在做的事。有了他，我们便可以免除于要把状态操作写得太明白的窘境。</p>
<a name="The_State_Monad"></a><h3>The State Monad</h3>


<p><code>Control.Monad.State</code> 这个模块提供了一个 <code>newtype</code> 包起来的型态。</p>
<pre class="code">newtype State s a = State { runState :: s -&gt; (a,s) }</pre>
<p>一个 <code>State s a</code> 代表的是一个改变状态的操作，他操纵的状态为型态 <code>s</code>，而产生的结果是 <code>a</code>。</p>

<p>我们已经见识过什么是改变状态的操作，以及他们是可以被看成具有 context 的值。接着来看看他们 <code>Monad</code> 的 instance：</p>
<pre class="code">instance Monad (State s) where  
    return x = State $ \s -&gt; (x,s)  
    (State h) &gt;&gt;= f = State $ \s -&gt; let (a, newState) = h s  
                                        (State g) = f a  
                                    in  g newState</pre>
<p>我们先来看看 <code>return</code> 那一行。我们 <code>return</code> 要作的事是接受一个值，并做出一个改变状态的操作，让他永远回传那个值。所以我们才做了一个 lambda 函数，<code>\s -&gt; (x,s)</code>。我们把 <code>x</code> 当成是结果，并且状态仍然是 <code>s</code>。这就是 <code>return</code> 要完成的 minimal context。</p>
<img src="../img/badge.png" alt="" style="float:right" class="floatright" />
<p>那 <code>&gt;&gt;=</code> 的实作呢？很明显的把改变状态的操作喂进 <code>&gt;&gt;=</code> 也必须要丢出另一个改变状态的操作。所以我们用 <code>State</code> 这个 <code>newtype</code> wrapper 来把一个 lambda 函数包住。这个 lambda 会是新的一个改变状态的操作。但里面的内容是什么？首先我们应该要从接受的操作取出结果。由于 lambda 是在一个大的操作中，所以我们可以喂给 <code>h</code> 我们现在的状态，也就是 <code>s</code>。那会产生 <code>(a, newState)</code>。到目前为止每次我们在实作 <code>&gt;&gt;=</code> 的时候，我们都会先从 monadic value 中取出结果，然后喂给 <code>f</code> 来得到新的 monadic value。在写 <code>Writer</code> 的时候，我们除了这样作还要确保 context 是用 <code>mappend</code> 把旧的 monoid value 跟新的接起来。在这边我们则是用 <code>f a</code> 得到一个新的操作 <code>g</code>。现在我们有了新的操作跟新的状态（叫做 <code>newState</code>），我们就把 <code>newState</code> 喂给 <code>g</code>。结果便是一个 tuple，里面包含了最后的结果跟最终的状态。</p>

<p>有了 <code>&gt;&gt;=</code>，我们便可以把两个操作黏在一起，只是第二个被放在一个函数中，专门接受第一个的结果。由于 <code>pop</code> 跟 <code>push</code> 已经是改变状态的操作了，我们可以把他们包在 <code>State</code> 中</p>
<pre class="code">import Control.Monad.State  
  
pop :: State Stack Int  
pop = State $ \(x:xs) -&gt; (x,xs)  

push :: Int -&gt; State Stack ()  
push a = State $ \xs -&gt; ((),a:xs)</pre>
<p><code>pop</code> 已经满足我们的条件，而 <code>push</code> 要先接受一个 <code>Int</code> 才会回传我们要的操作。所以我们可以改写先前的范例如下：</p>
<pre class="code">import Control.Monad.State  
  
stackManip :: State Stack Int  
stackManip = do  
  push 3  
  a &lt;- pop  
  pop</pre>
<p>看到我们是怎么把一个 <code>push</code> 跟两个 <code>pop</code> 黏成一个操作吗？当我们将他们从一个 <code>newtype</code> 取出，其实就是需要一个能喂进初始状态的函数：</p>
<pre class="code">ghci&gt; runState stackManip [5,8,2,1]  
(5,[8,2,1])</pre>
<p>我们不须绑定第二个 <code>pop</code>，因为我们根本不会用到 <code>a</code>，所以可以写成下面的样子：</p>
<pre class="code">stackManip :: State Stack Int  
stackManip = do  
    push 3  
    pop  
    pop</pre>
<p>再来尝试另外一种方式，先从堆叠上取下一个数字，看看他是不是 <code>5</code>，如果是的话就把他放回堆叠上，如果不是的话就堆上 <code>3</code> 跟 <code>8</code>。</p>
<pre class="code">stackStuff :: State Stack ()  
stackStuff = do  
    a &lt;- pop  
    if a == 5  
        then push 5  
        else do  
            push 3  
            push 8</pre>
<p>很直觉吧！我们来看看初始的堆叠的样子。</p>
<pre class="code">ghci&gt; runState stackStuff [9,0,2,1,0]  
((),[8,3,0,2,1,0])</pre>
<p>还记得我们说过 <code>do</code> 的结果会是一个 monadic value，而在 <code>State</code> monad 的 case，<code>do</code> 也就是一个改变状态的函数。而由于 <code>stackManip</code> 跟 <code>stackStuff</code> 都是改变状态的计算，因此我们可以把他们黏在一起：</p>
<pre class="code">moreStack :: State Stack ()  
moreStack = do  
    a &lt;- stackManip  
    if a == 100  
        then stackStuff  
        else return ()</pre>
<p>如果 <code>stackManip</code> 的结果是 <code>100</code>，我们就会跑 <code>stackStuff</code>，如果不是的话就什么都不做。<code>return ()</code> 不过就是什么是都不做，全部保持原样。</p>

<p><code>Contorl.Monad.State</code> 提供了一个 <code>MonadState</code> 的 typeclass，他有两个有用的函数，分别是 <code>get</code> 跟 <code>put</code>。对于 <code>State</code> 来说，<code>get</code> 的实作就像这样：</p>
<pre class="code">get = State $ \s -&gt; (s,s)</pre>
<p>他只是取出现在的状态除此之外什么也不做。而 <code>put</code> 函数会接受一个状态并取代掉现有的状态。</p>
<pre class="code">put newState = State $ \s -&gt; ((),newState)</pre>
<p>有了这两个状态，我们便可以看到现在堆叠中有什么，或是把整个堆叠中的元素换掉。</p>
<pre class="code">stackyStack :: State Stack ()  
stackyStack = do  
    stackNow &lt;- get  
    if stackNow == [1,2,3]  
        then put [8,3,1]  
        else put [9,2,1]</pre>
<p>我们可以看看对于 <code>State</code> 而言，<code>&gt;&gt;=</code> 的型态会是什么：</p>
<pre class="code">(&gt;&gt;=) :: State s a -&gt; (a -&gt; State s b) -&gt; State s b</pre>
<p>我们可以看到状态的型态都是 <code>s</code>，而结果从型态 <code>a</code> 变成型态 <code>b</code>。这代表我们可以把好几个改变状态的计算黏在一起，这些计算的结果可以都不一样，但状态的型态会是一样的。举例来说，对于 <code>Maybe</code> 而言，<code>&gt;&gt;=</code> 的型态会是：</p>
<pre class="code">(&gt;&gt;=) :: Maybe a -&gt; (a -&gt; Maybe b) -&gt; Maybe b</pre>
<p><code>Maybe</code> 不变是有道理的，但如果用 <code>&gt;&gt;=</code> 来把两种不同的 monad 接起来是没道理的。但对于 state monad 而言，monad 其实是 <code>State s</code>，所以如果 <code>s</code> 不一样，我们就要用 <code>&gt;&gt;=</code> 来把两个 monad 接起来。</p>
<a name="随机性与_state_monad"></a><h3>随机性与 state monad</h3>


<p>在章节的一开始，我们知道了在 Haskell 中要产生乱数的不方便。我们要拿一个产生器，并回传一个乱数跟一个新的产生器。接下来我们还一定要用新的产生器不可。但 State Monad 让我们可以方便一些。</p>

<p><code>System.Random</code> 中的 <code>random</code> 函数有下列的型态：</p>
<pre class="code">random :: (RandomGen g, Random a) =&gt; g -&gt; (a, g)</pre>
<p>代表他接受一个乱数产生器，并产生一个乱数跟一个新的产生器。很明显他是一个会改变状态的计算，所以我们可以用 <code>newtype</code> 把他包在一个 <code>State</code> 中，然后把他当作 monadic value 来操作。</p>
<pre class="code">import System.Random  
import Control.Monad.State  
  
randomSt :: (RandomGen g, Random a) =&gt; State g a  
randomSt = State random</pre>
<p>这样我们要丢三个硬币的结果可以改写成这样：</p>
<pre class="code">import System.Random  
import Control.Monad.State  
  
threeCoins :: State StdGen (Bool,Bool,Bool)  
threeCoins = do  
  a &lt;- randomSt  
  b &lt;- randomSt  
  c &lt;- randomSt  
  return (a,b,c)</pre>
<p><code>threeCoins</code> 是一个改变状态的计算，他接受一个初始的乱数产生器，他会把他喂给 <code>randomSt</code>，他会产生一个数字跟一个新的产生器，然后会一直传递下去。我们用 <code>return (a,b,c)</code> 来呈现 <code>(a,b,c)</code>，这样并不会改变最近一个产生器的状态。</p>
<pre class="code">ghci&gt; runState threeCoins (mkStdGen 33)  
((True,False,True),680029187 2103410263)</pre>
<p>要完成像这样要改变状态的任务便因此变得轻松了很多。</p>
<a name="Error_Monad"></a><h2>Error Monad</h2>


<p>我们知道 <code>Maybe</code> 是拿来赋予一个值具有可能失败的 context。一个值可能会是 <code>Just something</code> 或是一个 <code>Nothing</code>。尽管这很有用，但当我们拿到了一个 <code>Nothing</code>，我们只知道他失败了，但我们没办法塞进一些有用的信息，告诉我们究竟是在什么样的情况下失败了。</p>

<p>而 <code>Either e a</code> 则能让我们可以加入一个可能会发生错误的 context，还可以增加些有用的消息，这样能让我们知道究竟是什么东西出错了。一个 <code>Either e a</code> 的值可以是代表正确的 <code>Right</code>，或是代表错误的 <code>Left</code>，例如说：</p>
<pre class="code">ghci&gt; :t Right 4  
Right 4 :: (Num t) =&gt; Either a t  
ghci&gt; :t Left "out of cheese error"  
Left "out of cheese error" :: Either [Char] b</pre>
<p>这就像是加强版的 <code>Maybe</code>，他看起来实在很像一个 monad，毕竟他也可以当作是一个可能会发生错误的 context，只是多了些消息罢了。</p>

<p>在 <code>Control.Monad.Error</code> 里面有他的 <code>Monad</code> instance。</p>
<pre class="code">instance (Error e) =&gt; Monad (Either e) where  
    return x = Right x   
    Right x &gt;&gt;= f = f x  
    Left err &gt;&gt;= f = Left err  
    fail msg = Left (strMsg msg)</pre>
<p><code>return</code> 就是建立起一个最小的 context，由于我们用 <code>Right</code> 代表正确的结果，所以他把值包在一个 <code>Right</code> constructor 里面。就像实作 <code>Maybe</code> 时的 <code>return</code> 一样。</p>

<p><code>&gt;&gt;=</code> 会检查两种可能的情况：也就是 <code>Left</code> 跟 <code>Right</code>。如果进来的是 <code>Right</code>，那我们就调用 <code>f</code>，就像我们在写 <code>Just</code> 的时候一样，只是调用对应的函数。而在错误的情况下，<code>Left</code> 会被传出来，而且里面保有描述失败的值。</p>

<p><code>Either e</code> 的 <code>Monad</code> instance 有一项额外的要求，就是包在 <code>Left</code> 中的型态，也就是 <code>e</code>，必须是 <code>Error</code> typeclass 的 instance。<code>Error</code> 这个 typeclass 描述一个可以被当作错误消息的型态。他定义了 <code>strMsg</code> 这个函数，他接受一个用字串表达的错误。一个明显的范例就是 <code>String</code> 型态，当他是 <code>String</code> 的时候，<code>strMsg</code> 只不过回传他接受到的字串。</p>
<pre class="code">ghci&gt; :t strMsg  
strMsg :: (Error a) =&gt; String -&gt; a  
ghci&gt; strMsg "boom!" :: String  
"boom!"</pre>
<p>但因为我们通常在用 <code>Either</code> 来描述错误的时候，是用 <code>String</code> 来装错误消息，所以我们也不用担心这一点。当在 <code>do</code> 里面做 pattern match 失败的时候，<code>Left</code> 的值会拿来代表失败。</p>

<p>总之来看看一个范例吧：</p>
<pre class="code">ghci&gt; Left "boom" &gt;&gt;= \x -&gt; return (x+1)  
Left "boom"  
ghci&gt; Right 100 &gt;&gt;= \x -&gt; Left "no way!"  
Left "no way!"</pre>
<p>当我们用 <code>&gt;&gt;=</code> 来把一个 <code>Left</code> 喂进一个函数，函数的运算会被忽略而直接回传丢进去的 <code>Left</code> 值。当我们喂 <code>Right</code> 值给函数，函数就会被计算而得到结果，但函数还是产生了一个 <code>Left</code> 值。</p>

<p>当我们试着喂一个 <code>Right</code> 值给函数，而且函数也成功地计算，我们却碰到了一个奇怪的 type error。</p>
<pre class="code">ghci&gt; Right 3 &gt;&gt;= \x -&gt; return (x + 100)  
  
&lt;interactive&gt;:1:0:  
  Ambiguous type variable `a' in the constraints:  
    `Error a' arising from a use of `it' at &lt;interactive&gt;:1:0-33  
    `Show a' arising from a use of `print' at &lt;interactive&gt;:1:0-33  
  Probable fix: add a type signature that fixes these type variable(s)</pre>
<p>Haskell 警告说他不知道要为 <code>e</code> 选择什么样的型态，尽管我们是要印出 <code>Right</code> 的值。这是因为 <code>Error e</code> 被限制成 <code>Monad</code>。把 <code>Either</code> 当作 Monad 使用就会碰到这样的错误，你只要明确写出 type signature 就行了：</p>
<pre class="code">ghci&gt; Right 3 &gt;&gt;= \x -&gt; return (x + 100) :: Either String Int  
Right 103</pre>
<p>这样就没问题了。</p>

<p>撇除这个小毛病，把 <code>Either</code> 当 Monad 使用就像使用 <code>Maybe</code> 一样。在前一章中，我们展示了 <code>Maybe</code> 的使用方式。你可以把前一章的范例用 <code>Either</code> 重写当作练习。</p>
<a name="一些实用的_Moandic_functions"></a><h2>一些实用的 Moandic functions</h2>


<p>在这个章节，我们会看看一些操作 monadic value 的函数。这样的函数通常我们称呼他们为 monadic function。其中有些你是第一次见到，但有些不过是 <code>filter</code> 或 <code>foldl</code> 的变形。让我们来看看吧！</p>
<a name="liftM"></a><h3>liftM</h3>

<img src="../img/wolf.png" alt="" style="float:right" class="floatright" />
<p>当我们开始学习 Monad 的时候，我们是先学习 functors，他代表可以被 map over 的事物。接着我们学了 functors 的加强版，也就是 applicative functors，他可以对 applicative values 做函数的套用，也可以把一个一般值放到一个缺省的 context 中。最后，我们介绍在 applicative functors 上更进一步的 monad，他让这些具有 context 的值可以被喂进一般函数中。 </p>

<p>也就是说每一个 monad 都是个 applicative functor，而每一个 applicative functor 也都是一个 functor。<code>Applicative</code> typeclass 中有加入限制，让每一个 <code>Applicative</code> 都是 <code>Functor</code>。但 <code>Monad</code> 却没有这样的限制，让每个 <code>Monad</code> 都是 <code>Applicative</code>。这是因为 <code>Monad</code> 这个 typeclass 是在 <code>Applicative</code> 引入前就存在的缘故。</p>

<p>但即使每个 monad 都是一个 functor，但我们不需要依赖 <code>Functor</code> 的定义。那是因为我们有 <code>liftM</code> 这个函数。他会接受一个函数跟一个 monadic value，然后把函数 map over 那些 monadic value。所以他其实就是 <code>fmap</code>，以下是他的型态：</p>
<pre class="code">liftM :: (Monad m) =&gt; (a -&gt; b) -&gt; m a -&gt; m b</pre>
<p>而这是 <code>fmap</code> 的型态：</p>
<pre class="code">fmap :: (Functor f) =&gt; (a -&gt; b) -&gt; f a -&gt; f b</pre>
<p>如果 <code>Functor</code> 跟 <code>Monad</code> 的 instance 遵守 functor 跟 monad 的法则（到目前为止我们看过的 monad 都遵守），那这两个函数其实是等价的。这就像 <code>pure</code> 跟 <code>return</code> 其实是同一件事，只是一个在 <code>Applicative</code> 中，而另外一个在 <code>Monad</code> 里面，我们来试试看 <code>liftM</code> 吧：</p>
<pre class="code">ghci&gt; liftM (*3) (Just 8)  
Just 24  
ghci&gt; fmap (*3) (Just 8)  
Just 24  
ghci&gt; runWriter $ liftM not $ Writer (True, "chickpeas")  
(False,"chickpeas")  
ghci&gt; runWriter $ fmap not $ Writer (True, "chickpeas")  
(False,"chickpeas")  
ghci&gt; runState (liftM (+100) pop) [1,2,3,4]  
(101,[2,3,4])  
ghci&gt; runState (fmap (+100) pop) [1,2,3,4]  
(101,[2,3,4])</pre>
<p>我们已经知道 <code>fmap</code> 是如何运作在 <code>Maybe</code> 上。而 <code>liftM</code> 又跟 <code>fmap</code> 等价。对于 <code>Writer</code> 型态的值而言，函数只有对他的第一个 component 做处理。而对于改变状态的计算，<code>fmap</code> 跟 <code>liftM</code> 也都是产生另一个改变状态的计算。我们也看过了 <code>(+100)</code> 当作用在 <code>pop</code> 上会产生 <code>(1, [2,3,4])</code>。</p>

<p>来看看 <code>liftM</code> 是如何被实作的：</p>
<pre class="code">liftM :: (Monad m) =&gt; (a -&gt; b) -&gt; m a -&gt; m b  
liftM f m = m &gt;&gt;= (\x -&gt; return (f x))</pre>
<p>或者用 <code>do</code> 来表示得清楚些</p>
<pre class="code">liftM :: (Monad m) =&gt; (a -&gt; b) -&gt; m a -&gt; m b  
liftM f m = do  
    x &lt;- m  
    return (f x)</pre>
<p>我们喂一个 monadic value <code>m</code> 给函数，我们套用那个函数然后把结果放进一个缺省的 context。由于遵守 monad laws，这保证这操作不会改变 context，只会呈现最后的结果。我们可以看到实作中 <code>liftM</code> 也没有用到 <code>Functor</code> 的性质。这代表我们能只用 monad 提供给我们的就实作完 <code>fmap</code>。这特性让我们可以得到 monad 比 functor 性质要强的结论。</p>

<p><code>Applicative</code> 让我们可以操作具有 context 的值就像操作一般的值一样。</p>

<p>就像这样：</p>
<pre class="code">ghci&gt; (+) &lt;$&gt; Just 3 &lt;*&gt; Just 5  
Just 8  
ghci&gt; (+) &lt;$&gt; Just 3 &lt;*&gt; Nothing  
Nothing</pre>
<p>使用 applicative 的特性让事情变得很精简。</p>

<p><code>&lt;$&gt;</code> 不过就是 <code>fmap</code>，而 <code>&lt;*&gt;</code> 只是一个具有下列型态的函数：</p>
<pre class="code">(&lt;*&gt;) :: (Applicative f) =&gt; f (a -&gt; b) -&gt; f a -&gt; f b</pre>
<p>他有点像 <code>fmap</code>，只是函数本身有一个 context。我们必须把他从 context 中抽出，对 <code>f a</code> 做 map over 的东做，然后再放回 context 中。由于在 Haskel 中函数缺省都是 curried，我们便能用 <code>&lt;$&gt;</code> 以及 <code>&lt;*&gt;</code> 来让接受多个参数的函数也能接受 applicative 种类的值。</p>

<p>总之 <code>&lt;*&gt;</code> 跟 <code>fmap</code> 很类似，他也能只用 <code>Monad</code> 保证的性质实作出来。<code>ap</code> 这个函数基本上就是 <code>&lt;*&gt;</code>，只是他是限制在 <code>Monad</code> 上而不是 <code>Applicative</code> 上。这边是他的定义：</p>
<pre class="code">ap :: (Monad m) =&gt; m (a -&gt; b) -&gt; m a -&gt; m b  
ap mf m = do  
    f &lt;- mf  
    x &lt;- m  
    return (f x)</pre>
<p><code>mf</code> 是一个 monadic value，他的结果是一个函数。由于函数跟值都是放在 context 中，假设我们从 context 取出的函数叫 <code>f</code>，从 context 取出的值叫 <code>x</code>，我们把 <code>x</code> 喂给 <code>f</code> 然后再把结果放回 context。像这样：</p>
<pre class="code">ghci&gt; Just (+3) &lt;*&gt; Just 4  
Just 7  
ghci&gt; Just (+3) `ap` Just 4  
Just 7  
ghci&gt; [(+1),(+2),(+3)] &lt;*&gt; [10,11]  
[11,12,12,13,13,14]  
ghci&gt; [(+1),(+2),(+3)] `ap` [10,11]  
[11,12,12,13,13,14]</pre>
<p>由于我们能用 <code>Monad</code> 提供的函数实作出 <code>Applicative</code> 的函数，因此我们看到 Monad 有比 applicative 强的性质。事实上，当我们知道一个型态是 monad 的时候，大多数会先定义出 <code>Monad</code> 的 instance，然后才定义 <code>Applicative</code> 的 instance。而且只要把 <code>pure</code> 定义成 <code>return</code>，<code>&lt;*&gt;</code> 定义成 <code>ap</code> 就行了。同样的，如果你已经有了 <code>Monad</code> 的 instance，你也可以简单的定义出 <code>Functor</code>，只要把 <code>fmap</code> 定义成 <code>liftM</code> 就行了。</p>

<p><code>liftA2</code> 是一个方便的函数，他可以把两个 applicative 的值喂给一个函数。他的定义很简单：</p>
<pre class="code">liftA2 :: (Applicative f) =&gt; (a -&gt; b -&gt; c) -&gt; f a -&gt; f b -&gt; f c  
liftA2 f x y = f &lt;$&gt; x &lt;*&gt; y</pre>
<p><code>liftM2</code> 也是做差不多的事情，只是多了 <code>Monad</code> 的限制。在函式库中其实也有 <code>liftM3</code>，<code>liftM4</code> 跟 <code>liftM5</code>。</p>

<p>我们看到了 monad 相较于 applicative 跟 functor 有比较强的性质。尽管 moand 有 functor 跟 applicative functor 的性质，但他们不见得有 <code>Functor</code> 跟 <code>Applicative</code> 的 instance 定义。所以我们查看了一些在 monad 中定义，且等价于 functor 或 applicative functor 所具有的函数。</p>
<a name="The_join_function"></a><h3>The join function</h3>


<p>如果一个 monadic value 的结果是另一个 monadic value，也就是其中一个 monadic value 被包在另一个里面，你能够把他们变成一个普通的 monadic value 吗？就好像把他们打平一样。譬如说，我们有 <code>Just (Just 9)</code>，我们能够把他变成 <code>Just 9</code> 吗？事实上是可以的，这也是 monad 的一个性质。也就是我要看的 <code>join</code> 函数，他的型态是这样：</p>
<pre class="code">join :: (Monad m) =&gt; m (m a) -&gt; m a</pre>
<p>他接受一个包在另一个 monadic value 中的 monadic value，然后会回给我们一个普通的 monadic value。这边有一些 <code>Maybe</code> 的范例：</p>
<pre class="code">ghci&gt; join (Just (Just 9))  
Just 9  
ghci&gt; join (Just Nothing)  
Nothing  
ghci&gt; join Nothing  
Nothing</pre>
<p>第一行是一个计算成功的结果包在另一个计算成功的结果，他们应该要能结合成为一个比较大的计算成功的结果。第二行则是一个 <code>Nothing</code> 包在一个 <code>Just</code> 中。我们之前在处理 <code>Maybe</code> 型态的值时，会用 <code>&lt;*&gt;</code> 或 <code>&gt;&gt;=</code> 把他们结合起来。输入必须都是 <code>Just</code> 时结果出来才会是 <code>Just</code>。如果中间有任何的失败，结果就会是一个失败的结果。而第三行就是这样，我们尝试把失败的结果接合起来，结果也会是一个失败。</p>

<p>要 <code>join</code> 一个 list 也是很简单：</p>
<pre class="code">ghci&gt; join [[1,2,3],[4,5,6]]  
[1,2,3,4,5,6]</pre>
<p>你可以看到，对于 list 而言 <code>join</code> 不过就是 <code>concat</code>。</p>

<p>而要 <code>join</code> 一个包在 <code>Writer</code> 中的 <code>Writer</code>，</p>

<p>我们必须用 <code>mappend</code>：</p>
<pre class="code">ghci&gt; runWriter $ join (Writer (Writer (1,"aaa"),"bbb"))  
(1,"bbbaaa")</pre>
<p><code>"bbb"</code> 先被加到 monoid 中，接着 <code>"aaa"</code> 被附加上去。你想要查看 <code>Writer</code> 中的值的话，必须先把值写进去才行。</p>

<p>要对 <code>Either</code> 做 <code>join</code> 跟对 <code>Maybe</code> 做 <code>join</code> 是很类似的：</p>
<pre class="code">ghci&gt; join (Right (Right 9)) :: Either String Int  
Right 9  
ghci&gt; join (Right (Left "error")) :: Either String Int  
Left "error"  
ghci&gt; join (Left "error") :: Either String Int  
Left "error"</pre>
<p>如果我们对一个包了另外一个改变状态的计算的进行改变状态的计算，要作 <code>join</code> 的动作会让外面的先被计算，然后才是计算里面的：</p>
<pre class="code">ghci&gt; runState (join (State $ \s -&gt; (push 10,1:2:s))) [0,0,0]  
((),[10,1,2,0,0,0])</pre>
<p>这边的 lambda 函数接受一个状态，并把 <code>2</code> 跟 <code>1</code> 放到堆叠中，并把 <code>push 10</code> 当作他的结果。当对整个东西做 <code>join</code> 的时候，他会先把 <code>2</code> 跟 <code>1</code> 放到堆叠上，然后进行 <code>push 10</code> 的计算，因而把 <code>10</code> 放到堆叠的顶端。</p>

<p><code>join</code> 的实作像是这样：</p>
<pre class="code">join :: (Monad m) =&gt; m (m a) -&gt; m a  
join mm = do  
    m &lt;- mm  
    m</pre>
<p>因为 <code>mm</code> 的结果会是一个 monadic value，我们单独用 <code>m &lt;- mm</code> 拿取他的结果。这也可以说明 <code>Maybe</code> 只有当外层跟内层的值都是 <code>Just</code> 的时候才会是 <code>Just</code>。如果把 <code>mm</code> 的值设成 <code>Just (Just 8)</code> 的话，他看起来会是这样：</p>
<pre class="code">joinedMaybes :: Maybe Int  
joinedMaybes = do  
    m &lt;- Just (Just 8)  
    m</pre><img src="../img/tipi.png" alt="" style="float:right" class="floatright" />
<p>最有趣的是对于一个 monadic value 而言，用 <code>&gt;&gt;=</code> 把他喂进一个函数其实等价于对 monad 做 mapping over 的动作，然后用 <code>join</code> 来把值从 nested 的状态变成扁平的状态。也就是说 <code>m &gt;&gt;= f</code> 其实就是 <code>join (fmap f m)</code>。如果你仔细想想的话其实很明显。<code>&gt;&gt;=</code> 的使用方式是，把一个 monadic value 喂进一个接受普通值的函数，但他却会回传 monadic value。如果我们 map over 一个 monadic value，我们会做成一个 monadic value 包了另外一个 monadic value。例如说，我们现在手上有 <code>Just 9</code> 跟 <code>\x -&gt; Just (x+1)</code>。如果我们把这个函数 map over <code>Just 9</code>，我们会得到 <code>Just (Just 10)</code></p>

<p>事实上 <code>m &gt;&gt;= f</code> 永远等价于 <code>join (fmap f m)</code> 这性质非常有用。如果我们要定义自己的 <code>Monad</code> instance，要知道怎么把 nested monadic value 变成扁平比起要定义 <code>&gt;&gt;=</code> 是比较容易的一件事。</p>
<a name="filterM"></a><h3>filterM</h3>


<p><code>filter</code> 函数是 Haskell 中不可或缺的要素。他接受一个断言(predicate)跟一个 list 来过滤掉断言为否的部份并回传一个新的 list。他的型态是这样：</p>
<pre class="code">filter :: (a -&gt; Bool) -&gt; [a] -&gt; [a]</pre>
<p>predicate 能接 list 中的一个元素并回传一个 <code>Bool</code> 型态的值。但如果 <code>Bool</code> 型态其实是一个 monadic value 呢？也就是他有一个 context。例如说除了 <code>True</code> 跟 <code>False</code> 之外还伴随一个 monoid，像是 <code>["Accepted the number 5"]</code>，或 <code>["3 is too small"]</code>。照前面所学的听起来是没问题，而且产出的 list 也会跟随 context，在这个例子中就是 log。所以如果 <code>Bool</code> 会回传伴随 context 的布林值，我们会认为最终的结果也会具有 context。要不然这些 context 都会在处理过程中遗失。</p>

<p>在 <code>Control.Monad</code> 中的 <code>filterM</code> 函数正是我们所需要的，他的型态如下：</p>
<pre class="code">filterM :: (Monad m) =&gt; (a -&gt; m Bool) -&gt; [a] -&gt; m [a]</pre>
<p>predicate 会回传一个 monadic value，他的结果会是 <code>Bool</code> 型态，由于他是 monadic value，他的 context 有可能会是任何 context，譬如说可能的失败，non-determinism，甚至其他的 context。一旦我们能保证 context 也会被保存在最后的结果中，结果也就是一个 monadic value。</p>

<p>我们来写一个接受 list 然后过滤掉小于 4 的函数。先尝试使用 <code>filter</code> 函数：</p>
<pre class="code">ghci&gt; filter (\x -&gt; x &lt; 4) [9,1,5,2,10,3]  
[1,2,3]</pre>
<p>很简单吧。接着我们在做个 predicate，除了表达 <code>True</code> 或 <code>False</code> 之外，还提供了一个 log。我们会用 <code>Writer</code> monad 来表达这件事：</p>
<pre class="code">keepSmall :: Int -&gt; Writer [String] Bool  
keepSmall x  
    | x &lt; 4 = do  
        tell ["Keeping " ++ show x]  
        return True  
    | otherwise = do  
        tell [show x ++ " is too large, throwing it away"]  
        return False</pre>
<p>这个函数会回传 <code>Writer [String] Bool</code> 而不是一个单纯的 <code>Bool</code>。他是一个 monadic predicate。如果扫到的数字小于 <code>4</code> 的话，我们就会回报要保存他，而且回传 <code>return True</code>。</p>

<p>接着，我们把他跟一个 list 喂给 <code>filterM</code>。由于 predicate 会回传 <code>Writer</code>，所以结果仍会是一个 <code>Writer</code> 值。</p>
<pre class="code">ghci&gt; fst $ runWriter $ filterM keepSmall [9,1,5,2,10,3]  
[1,2,3]</pre>
<p>要检查 <code>Writer</code> 的结果，我们想要印出 log 看看里面有什么东西：</p>
<pre class="code">ghci&gt; mapM_ putStrLn $ snd $ runWriter $ filterM keepSmall [9,1,5,2,10,3]  
9 is too large, throwing it away  
Keeping 1  
5 is too large, throwing it away  
Keeping 2  
10 is too large, throwing it away  
Keeping 3</pre>
<p>提供 monadic predicate 给 <code>filterM</code>，我们便能够做 filter 的动作，同时还能保有 monadic context。</p>

<p>一个比较炫的技巧是用 <code>filterM</code> 来产生一个 list 的 powerset。一个 powerset 就是一个集合所有子集所形成的集合。如果说我们的 list 是 <code>[1,2,3]</code>，那他个 powerset 就会是：</p>
<pre class="code">[1,2,3]  
[1,2]  
[1,3]  
[1]  
[2,3]  
[2]  
[3]  
[]</pre>
<p>换句话说，要产生一个 powerset 就是要列出所有要丢掉跟保留的组合。<code>[2,3]</code> 只不过代表我们把 <code>1</code> 给丢掉而已。</p>

<p>我们要依赖 non-determinism 来写我们这产生 powerset 的函数。我们接受一个 list <code>[1,2,3]</code> 然后查看第一个元素，这个例子中是 <code>1</code>，我们会问：我们要保留他呢？还是丢掉他呢？答案是我们都要做。所以我们会用一个 non-determinism 的 predicate 来过滤我的 list。也就是我们的 <code>powerset</code> 函数：</p>
<pre class="code">powerset :: [a] -&gt; [[a]]  
powerset xs = filterM (\x -&gt; [True, False]) xs</pre>
<p>等等，我们已经写完了吗？没错，就这么简单，我们可以同时丢掉跟保留每个元素。只要我们用 non-deterministic predicate，那结果也就是一个 non-deterministic value，也便是一个 list 的 list。试着跑跑看：</p>
<pre class="code">ghci&gt; powerset [1,2,3]  
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]</pre>
<p>这样的写法需要让你好好想一下，但如果你能接受 list 其实就是 non-deterministic value 的话，那要想通会比较容易一些。</p>
<a name="foldM"></a><h3>foldM</h3>


<p><code>foldl</code> 的 monadic 的版本叫做 <code>foldM</code>。如果你还有印象的话，<code>foldl</code> 会接受一个 binary 函数，一个起始累加值跟一串 list，他会从左边开始用 binary 函数每次带进一个值来 fold。<code>foldM</code> 也是做同样的事，只是他接受的这个 binary 函数会产生 monadic value。不意外的，他的结果也会是 monadic value。<code>foldl</code> 的型态是：</p>
<pre class="code">foldl :: (a -&gt; b -&gt; a) -&gt; a -&gt; [b] -&gt; a</pre>
<p>而 <code>foldM</code> 的型态则是：</p>
<pre class="code">foldM :: (Monad m) =&gt; (a -&gt; b -&gt; m a) -&gt; a -&gt; [b] -&gt; m a</pre>
<p>binary 函数的回传值是 monadic，所以结果也会是 monadic。我们来试着把 list 的值用 fold 全部加起来：</p>
<pre class="code">ghci&gt; foldl (\acc x -&gt; acc + x) 0 [2,8,3,1]  
14</pre>
<p>这边起始的累加值是 <code>0</code>，首先 <code>2</code> 会被加进去，变成 <code>2</code>。然后 <code>8</code> 被加进去变成 <code>10</code>，直到我们没有值可以再加，那便是最终的结果。</p>

<p>但如果我们想额外加一个条件，也就是当碰到一个数字大于 <code>9</code> 时候，整个运算就算失败呢？一种合理的修改就是用一个 binary 函数，他会检查现在这个数是否大于 <code>9</code>，如果是便引发失败，如果不是就继续。由于有失败的可能性，我们便需要这个 binary 函数回传一个 <code>Maybe</code>，而不是一个普通的值。我们来看看这个函数：</p>
<pre class="code">binSmalls :: Int -&gt; Int -&gt; Maybe Int  
binSmalls acc x  
    | x &gt; 9     = Nothing  
    | otherwise = Just (acc + x)</pre>
<p>由于这边的 binary 函数是 monadic function，我们不能用普通的 <code>foldl</code>，我们必须用 <code>foldM</code>：</p>
<pre class="code">ghci&gt; foldM binSmalls 0 [2,8,3,1]  
Just 14  
ghci&gt; foldM binSmalls 0 [2,11,3,1]  
Nothing</pre>
<p>由于这串 list 中有一个数值大于 <code>9</code>，所以整个结果会是 <code>Nothing</code>。另外你也可以尝试 fold 一个回传 <code>Writer</code> 的 binary 函数，他会在 fold 的过程中纪录你想纪录的信息。</p>
<a name="Making_a_safe_RPN_calculator"></a><h3>Making a safe RPN calculator</h3>

<img src="../img/miner.png" alt="" style="float:left" class="floatleft" />
<p>之前的章节我们实作了一个 RPN 计算机，但我们没有做错误的处理。他只有在输入是合法的时候才会运算正确。假如有东西出错了，整个程序便会当掉。我们在这章看到了要怎样把代码转换成 monadic 的版本，我们先尝适用 <code>Maybe</code> monad 来帮我们的 RPN 计算机加上些错误处理。</p>

<p>我们的 RPN 计算机接受一个像 <code>"1 3 + 2 *"</code> 这样的字串，把他断成 word，变成 <code>["1","3","+","2","*"]</code> 这样。然后用一个 binary 函数，跟一个空的堆叠，从左边开始或是将数值推进堆叠中，或是操作堆叠最上层的两个元素。</p>

<p>以下便是程序的内核部份：</p>
<pre class="code">import Data.List  
  
solveRPN :: String -&gt; Double  
solveRPN = head . foldl foldingFunction [] . words</pre>
<p>我们把输入变成一个字串的 list，从左边开始 fold，当堆叠中只剩下一个元素的时候，他便是我们要的答案。以下是我们的 folding 函数：</p>
<pre class="code">foldingFunction :: [Double] -&gt; String -&gt; [Double]  
foldingFunction (x:y:ys) "*" = (x * y):ys  
foldingFunction (x:y:ys) "+" = (x + y):ys  
foldingFunction (x:y:ys) "-" = (y - x):ys  
foldingFunction xs numberString = read numberString:xs</pre>
<p>这边我们的累加元素是一个堆叠，我们用一个 <code>Double</code> 的 list 来表示他。当我们在做 folding 的过程，如果当前的元素是一个 operator，他会从堆叠上拿下两个元素，用 operator 施行运算然后把结果放回堆叠。如果当前的元素是一个表示成字串的数字，他会把字串转换成数字，并回传一个新的堆叠包含了转换后的数字。</p>

<p>我们首先把我们的 folding 函数加上处理错误的 case，所以他的型态会变成这样：</p>
<pre class="code">foldingFunction :: [Double] -&gt; String -&gt; Maybe [Double]</pre>
<p>他不是回传一个 <code>Just</code> 的堆叠就是回传 <code>Nothing</code>。</p>

<p><code>reads</code> 函数就像 <code>read</code> 一样，差别在于他回传一个 list。在成功读取的情况下 list 中只包含读取的那个元素。如果他失败了，他会回传一个空的 list。除了回传读取的元素，他也回传剩下读取失败的元素。他必须要看完整串输入，我们想把他弄成一个 <code>readMaybe</code> 的函数，好方便我们进行。</p>
<pre class="code">readMaybe :: (Read a) =&gt; String -&gt; Maybe a  
readMaybe st = case reads st of [(x,"")] -&gt; Just x  
                                _ -&gt; Nothing</pre>
<p>测试结果如下：</p>
<pre class="code">ghci&gt; readMaybe "1" :: Maybe Int  
Just 1  
ghci&gt; readMaybe "GO TO HELL" :: Maybe Int  
Nothing</pre>
<p>看起来运作正常。我们再把他变成一个可以处理失败情况的 monadic 函数</p>
<pre class="code">foldingFunction :: [Double] -&gt; String -&gt; Maybe [Double]  
foldingFunction (x:y:ys) "*" = return ((x * y):ys)  
foldingFunction (x:y:ys) "+" = return ((x + y):ys)  
foldingFunction (x:y:ys) "-" = return ((y - x):ys)  
foldingFunction xs numberString = liftM (:xs) (readMaybe numberString)</pre>
<p>前三种 case 跟前面的很像，只差在堆叠现在是包在 <code>Just</code> 里面（我们常常是用 <code>return</code> 来做到这件事，但其实我们也可以用 <code>Just</code>）。在最后一种情况，我们用 <code>readMaybe numberString</code> 然后我们用 <code>(:xs)</code> map over 他。所以如果堆叠 <code>xs</code> 是 <code>[1.0,2.0]</code> 且 <code>readMaybe numberString</code> 产生 <code>Just 3.0</code>，那结果便是 <code>Just [3.0,1.0,2.0]</code>。如果 <code>readyMaybe numberString</code> 产生 <code>Nothing</code> 那结果便是 <code>Nothing</code>。我们来试着跑跑看 folding 函数</p>
<pre class="code">ghci&gt; foldingFunction [3,2] "*"  
Just [6.0]  
ghci&gt; foldingFunction [3,2] "-"  
Just [-1.0]  
ghci&gt; foldingFunction [] "*"  
Nothing  
ghci&gt; foldingFunction [] "1"  
Just [1.0]  
ghci&gt; foldingFunction [] "1 wawawawa"  
Nothing</pre>
<p>看起来正常运作。我们可以用他来写一个新的 <code>solveRPN</code>。</p>
<pre class="code">import Data.List  
  
solveRPN :: String -&gt; Maybe Double  
solveRPN st = do  
  [result] &lt;- foldM foldingFunction [] (words st)  
  return result</pre>
<p>我们仍是接受一个字串把他断成一串 word。然后我们用一个空的堆叠来作 folding 的动作，只差在我们用的是 <code>foldM</code> 而不是 <code>foldl</code>。<code>foldM</code> 的结果会是 <code>Maybe</code>，<code>Maybe</code> 里面包含了一个只有一个元素的 list。我们用 <code>do</code> expression 来取出值，把他绑定到 <code>result</code> 上。当 <code>foldM</code> 回传 <code>Nothing</code> 的时候，整个结果就变成 <code>Nothing</code>。也特别注意我们有在 <code>do</code> 里面做 pattern match 的动作，所以如果 list 中不是只有一个元素的话，最后结果便会是 <code>Nothing</code>。最后一行我们用 <code>return result</code> 来展示 RPN 计算的结果，把他包在一个 <code>Maybe</code> 里面。</p>
<pre class="code">ghci&gt; solveRPN "1 2 * 4 +"  
Just 6.0  
ghci&gt; solveRPN "1 2 * 4 + 5 *"  
Just 30.0  
ghci&gt; solveRPN "1 2 * 4"  
Nothing  
ghci&gt; solveRPN "1 8 wharglbllargh"  
Nothing</pre>
<p>第一个例子会失败是因为 list 中不是只有一个元素，所以 <code>do</code> 里面的 pattern matching 失败了。第二个例子会失败是因为 <code>readMaybe</code> 回传了 <code>Nothing</code>。</p>
<a name="Composing_monadic_functions"></a><h3>Composing monadic functions</h3>


<p>当我们介绍 monad law 的时候，我们说过 <code>&lt;=&lt;</code> 就像是函数合成一样，只差在一个是作用在普通函数 <code>a -&gt; b</code>。一个是作用在 monadic 函数 <code>a -&gt; m b</code>。</p>
<pre class="code">ghci&gt; let f = (+1) . (*100)  
ghci&gt; f 4  
401  
ghci&gt; let g = (\x -&gt; return (x+1)) &lt;=&lt; (\x -&gt; return (x*100))  
ghci&gt; Just 4 &gt;&gt;= g  
Just 401</pre>
<p>在这个例子中我们合成了两个普通的函数，并喂给给他 <code>4</code>。我们也合成了两个 monadic 函数并用 <code>&gt;&gt;=</code> 喂给他 <code>Just 4</code>。</p>

<p>如果我们在 list 中有一大堆函数，我们可以把他们合成一个巨大的函数。用 <code>id</code> 当作累加的起点，<code>.</code> 当作 binary 函数，用 fold 来作这件事。</p>
<pre class="code">ghci&gt; let f = foldr (.) id [(+1),(*100),(+1)]  
ghci&gt; f 1  
201</pre>
<p><code>f</code> 接受一个数字，然后会帮他加 <code>1</code>，乘以 <code>100</code>，再加 <code>1</code>。我们也可以将 monadic 函数用同样的方式做合成，只是不用 <code>.</code> 而用 <code>&lt;=&lt;</code>，不用 <code>id</code> 而用 <code>return</code>。我们不需要 <code>foldM</code>，由于 <code>&lt;=&lt;</code> 只用 <code>foldr</code> 就足够了。</p>

<p>当我们在之前的章节介绍 list monad 的时候， 我们用他来解决一个骑士是否能在三步内走到另一点的问题。 那个函数叫做 <code>moveKnight</code>， 他接受一个座标然后回传所有可能的下一步。 然后产生出所有可能三步的移动。</p>
<pre class="code">in3 start = return start &gt;&gt;= moveKnight &gt;&gt;= moveKnight &gt;&gt;= moveKnight</pre>
<p>要检查我们是否能只用三步从 <code>start</code> 走到 <code>end</code>，我们用下列函数</p>
<pre class="code">canReachIn3 :: KnightPos -&gt; KnightPos -&gt; Bool  
canReachIn3 start end = end `elem` in3 start</pre>
<p>如果使用 monadic 版本的合成的话，我们也可以做一个类似的 <code>in3</code>，但我们希望他不只有三步的版本，而希望有任意步的版本。如果你仔细观察 <code>in3</code>，他只不过用 <code>&gt;&gt;=</code> 跟 <code>moveKnight</code> 把之前所有可能结果喂到下一步。把他一般化，就会像下面的样子：</p>
<pre class="code">import Data.List  
  
inMany :: Int -&gt; KnightPos -&gt; [KnightPos]  
inMany x start = return start &gt;&gt;= foldr (&lt;=&lt;) return (replicate x moveKnight)</pre>
<p>首先我们用 <code>replicate</code> 来做出一个 list，里面有 <code>x</code> 份的 <code>moveKnight</code>。然后我们把所有函数都合成起来，就会给我们从起点走 <code>x</code> 步内所有可能的的位置。然后我们只需要把起始位置喂给他就好了。</p>

<p>我们也可以一般化我们的 <code>canReachIn3</code>：</p>
<pre class="code">canReachIn :: Int -&gt; KnightPos -&gt; KnightPos -&gt; Bool  
canReachIn x start end = end `elem` inMany x start</pre><a name="定义自己的_Monad"></a><h2>定义自己的 Monad</h2>

<img src="../img/spearhead.png" alt="" style="float:none" class="floatnone" />
<p>在这一章节，我们会带你看看究竟一个型态是怎么被辨认，确认是一个 monad 而且正确定义出 <code>Monad</code> 的 instance。我们通常不会为了定义 monad 而定义。比较常发生的是，我们想要针对一个问题建立模型，却稍后发现我们定义的型态其实是一个 Monad，所以就定义一个 <code>Monad</code> 的 instance。</p>

<p>正如我们看到的，list 是被拿来当作 non-deterministic values。对于 <code>[3,5,9]</code>，我们可以看作是一个 non-deterministic value，我们不能知道究竟是哪一个。当我们把一个 list 用 <code>&gt;&gt;=</code> 喂给一个函数，他就是把一串可能的选择都丢给函数，函数一个个去计算在那种情况下的结果，结果也便是一个 list。</p>

<p>如果我们把 <code>[3,5,9]</code> 看作是 <code>3</code>,<code>5</code>,<code>9</code> 各出现一次，但这边没有每一种数字出现的机率。如果我们把 non-deterministic 的值看作是 <code>[3,5,9]</code>，但 <code>3</code> 出现的机率是 50%，<code>5</code> 跟 <code>9</code> 出现的机率各是 25%呢？我们来试着用 Haskell 描述看看。</p>

<p>如果说 list 中的每一个元素都伴随着他出现的机率。那下面的形式就蛮合理的：</p>
<pre class="code">[(3,0.5),(5,0.25),(9,0.25)]</pre>
<p>在数学上，机率通常不是用百分比表示，而是用介于 0 跟 1 的实数表示。0 代表不可能会发生，而 1 代表绝对会发生。但浮点数很有可能很快随着运算失去精准度，所以 Haskell 有提供有理数。他的型态是摆在 <code>Data.Ratio</code> 中，叫做 <code>Rational</code>。要创造出一个 <code>Rational</code>，我们会把他写成一个分数的形式。分子跟分母用 <code>%</code> 分隔。这边有几个例子：</p>
<pre class="code">ghci&gt; 1%4  
1 % 4  
ghci&gt; 1%2 + 1%2  
1 % 1  
ghci&gt; 1%3 + 5%4  
19 % 12</pre>
<p>第一行代表四分之一，第二行代表两个二分之一加起来变成一。而第三行我们把三分之一跟四分之五加起来变成十二分之十九。所以我们来用 <code>Rational</code> 取代浮点数来当作我们的机率值吧。</p>
<pre class="code">ghci&gt; [(3,1%2),(5,1%4),(9,1%4)]  
[(3,1 % 2),(5,1 % 4),(9,1 % 4)]</pre>
<p>所以 <code>3</code> 有二分之一的机会出现，而 <code>5</code> 跟 <code>9</code> 有四分之一的机会出现。</p>

<p>可以看到我们帮 list 加上了一些额外的 context。再我们继续深入之前，我们用一个 <code>newtype</code> 把他包起来，好让我们帮他写 instance。</p>
<pre class="code">import Data.Ratio

newtype Prob a = Prob { getProb :: [(a,Rational)] } deriving Show</pre>
<p>接着我们想问，这是一个 functor 吗？list 是一个 functor，所以很有可能他也是一个 functor，毕竟我们只是在 list 上多加一些东西而已。在 list 的情况下，我们可以针对每个元素用函数做处理。这边我们也是用函数针对每个元素做处理，只是我们是输出机率值。所以我们就来写个 functor 的 instance 吧。</p>
<pre class="code">instance Functor Prob where  
    fmap f (Prob xs) = Prob $ map (\(x,p) -&gt; (f x,p)) xs</pre>
<p>我们可以用 pattern matching 的方式把 <code>newtype</code> 解开来，套用函数 <code>f</code> 之后再包回去。过程中不会动到机率值。</p>
<pre class="code">ghci&gt; fmap negate (Prob [(3,1%2),(5,1%4),(9,1%4)])  
Prob {getProb = [(-3,1 % 2),(-5,1 % 4),(-9,1 % 4)]}</pre>
<p>要注意机率的和永远是 <code>1</code>。如果我们没有漏掉某种情形的话，没有道理他们加起来的值不为 <code>1</code>。一个有 75% 机率是正面以及 50% 机率是反面的硬币根本没什么道理。</p>

<p>接着要问一个重要的问题，他是一个 monad 吗？我们知道 list 是一个 monad，所以他很有可能也是一个 monad。首先来想想 <code>return</code>。他在 list 是怎么运作的？他接受一个普通的值并把他放到一个 list 中变成只有一个元素的 list。那在这边又如何？由于他是一个最小的 context，他也应该是一个元素的 list。那机率值呢？<code>return x</code> 的值永远都是 <code>x</code>，所以机率值不应该是 <code>0</code>，而应该是 <code>1</code>。</p>

<p>至于 <code>&gt;&gt;=</code> 呢？看起来有点复杂，所以我们换种方式来思考，我们知道 <code>m &gt;&gt;= f</code> 会等价于 <code>join (fmap f m)</code>，所以我们来想要怎么把一串包含 probability list 的 list 弄平。举个例子，考虑一个 list，<code>'a'</code> 跟 <code>'b'</code> 恰出现其中一个的机率为 25%，两个出现的机率相等。而 <code>'c'</code> 跟 <code>'d'</code> 恰出现其中一个的机率为 75%，两个出现的机率也是相等。这边有一个图将情形画出来。</p>
<img src="../img/prob.png" alt="" style="float:left" class="floatleft" />
<p>每个字母发生的机率有多高呢？如果我们用四个盒子来代表每个字母，那每个盒子的机率为何？每个盒子的机率是他们所装有的机率值相乘的结果。<code>'a'</code> 的机率是八分之一，<code>'b'</code> 同样也是八分之一。八分之一是因为我们把二分之一跟四分之一相乘得到的结果。而 <code>'c'</code> 发生的机率是八分之三，是因为二分之一乘上四分之三。<code>'d'</code> 同样也是八分之三。如果把所有的机率加起来，就会得到一，符合机率的规则。</p>

<p>来看看怎么用一个 list 表达我们要说明的东西：</p>
<pre class="code">thisSituation :: Prob (Prob Char)  
thisSituation = Prob  
    [( Prob [('a',1%2),('b',1%2)] , 1%4 )  
    ,( Prob [('c',1%2),('d',1%2)] , 3%4 )  
    ]</pre>
<p>注意到这边的型态是 <code>Prob (Prob Char)</code>。所以我们要思考的是如何把一串包含机率 list 的 list 打平。如果能成功写出这样的逻辑，<code>&gt;&gt;=</code> 不过就是 <code>join (fmap f m)</code>，我们便得到了一个 monad。我们这边写了一个 <code>flatten</code> 来做这件事。</p>
<pre class="code">flatten :: Prob (Prob a) -&gt; Prob a  
flatten (Prob xs) = Prob $ concat $ map multAll xs  
    where multAll (Prob innerxs,p) = map (\(x,r) -&gt; (x,p*r)) innerxs</pre>
<p><code>multAll</code> 接受一个 tuple，里面包含一个 probability list 跟一个伴随的机率值 <code>p</code>，所以我们要作的事是把 list 里面的机率值都乘以 <code>p</code>，并回传一个新的 tuple 包含新的 list 跟新的机率值。我们将 <code>multAll</code> map over 到我们的 probability list 上，我们就成功地打平了我们的 list。</p>

<p>现在我们就能定义我们的 <code>Monad</code> instance。</p>
<pre class="code">instance Monad Prob where  
    return x = Prob [(x,1%1)]  
    m &gt;&gt;= f = flatten (fmap f m)  
    fail _ = Prob []</pre><img src="../img/ride.png" alt="" style="float:right" class="floatright" />
<p>由于我们已经把所有苦工的做完了，定义这个 instance 显得格外轻松。我们也定义了 <code>fail</code>，我们定义他的方式跟定义 list 一样。如果在 <code>do</code> 中发生了失败的 pattern match，那就会调用 <code>fail</code>。</p>

<p>检查我们定义的 instance 是否遵守 monad law 也是很重要的。monad law 的第一个定律是 <code>return x &gt;&gt;= f</code> 应该要等价于 <code>f x</code>。要写出严格的证明会很麻烦，但我们可以观察到下列事实：首先用 <code>return</code> 做一个最小的 context，然后用 <code>fmap</code> 将一个函数 map over 这个 context，再将他打平。这样做出来的 probability list，每一个机率值都相当于将我们最初放到 minimal context 中的值乘上 <code>1%1</code>。同样的逻辑，也可以看出 <code>m &gt;&gt;= return</code> 是等价于 <code>m</code>。第三个定律是 <code>f &lt;=&lt; (g &lt;=&lt; h)</code> 应该要等价于 <code>(f &lt;=&lt; g) &lt;=&lt; h</code>。我们可以从乘法有结合律的性质，以及 list monad 的特性上推出 probability monad 也符合这个定律。<code>1%2 * (1%3 * 1%5)</code> 等于 <code>(1%2 * 1%3) * 1%5</code>。</p>

<p>现在我们有了一个 monad，这样有什么好处呢？他可以帮助我们计算机率值。我们可以把机率事件看作是具有 context 的 value，而 probability monad 可以保证机率值能正确地被计算成最终的结果。</p>

<p>好比说我们现在有两个普通的硬币以及一个灌铅的硬币。灌铅的硬币十次中有九次会出现正面，只有一次会出现反面。如果我们一次丢掷这三个硬币，有多大的机会他们都会出现正面呢？让我们先来表达丢掷硬币这件事，分别丢的是灌铅的跟普通的硬币。</p>
<pre class="code">data Coin = Heads | Tails deriving (Show, Eq)  

coin :: Prob Coin  
coin = Prob [(Heads,1%2),(Tails,1%2)]  

loadedCoin :: Prob Coin  
loadedCoin = Prob [(Heads,1%10),(Tails,9%10)]</pre>
<p>最后，来看看掷硬币的函数：</p>
<pre class="code">import Data.List (all)  
  
flipThree :: Prob Bool  
flipThree = do  
  a &lt;- coin  
  b &lt;- coin  
  c &lt;- loadedCoin  
  return (all (==Tails) [a,b,c])</pre>
<p>试着跑一下的话，我们会看到尽管我们用了不公平的硬币，三个反面的机率还是不高。</p>
<pre class="code">ghci&gt; getProb flipThree  
[(False,1 % 40),(False,9 % 40),(False,1 % 40),(False,9 % 40),  
 (False,1 % 40),(False,9 % 40),(False,1 % 40),(True,9 % 40)]</pre>
<p>同时出现正面的机率是四十分之九，差不多是 25%的机会。我们的 monad 并没有办法 join 所有都是 <code>False</code> 的情形，也就是所有硬币都是出现反面的情况。不过那不是个严重的问题，可以写个函数来将同样的结果变成一种结果，这就留给读者当作习题。</p>

<p>在这章节中，我们从提出问题到真的写出型态，并确认这个型态是一个 monad，写出他的 instance 并实际操作他。这是个很棒的经验。现在读者们应该对于 monad 有不少的了解才是。</p>

            <ul class="nav">
                <li class="left">  <img src="../img/prv.png" alt="prev" /><a href="a-fistful-of-monads.html">来看看几种 Monad</a></li>
                <li class="center"><a href="chapters.html">目录</a></li>
                <li class="right"> <a href="zippers.html">Zippers 数据结构</a><img src="../img/nxt.png" alt="next" /></li>
            </ul>
        </div>
        <div id="footer">
        </div>
        <div id="feedback">Send feedback</div>
    </body>
</html>
